Characterising Bounded Expansion by Neighbourhood Complexity
作者： Felix Reidl , Fernando Sánchez Villaamil , Konstantinos Stavropoulos
DOI:
关键词:
摘要: We show that a graph class $\cal G$ has bounded expansion if and only it $r$-neighbourhood complexity, i.e. for any vertex set $X$ of subgraph $H$ $G\in\cal G$, the number subsets which are exact $r$-neighbourhoods vertices on is linear to size $X$. This established by bounding complexity in terms both its $r$-centred colouring weak $r$-colouring number, provide known characterisations property expansion.
arxiv.org参考文章(27)
Anuj Dawar, Martin Grohe, Stephan Kreutzer, Locally Excluding a Minor logic in computer science. pp. 270- 279 ,(2007) , 10.1109/LICS.2007.31
Martin Grohe, Dániel Marx, Structure theorem and isomorphism test for graphs with excluded topological subgraphs Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 173- 192 ,(2012) , 10.1145/2213977.2213996
Guillaume Fertin, André Raspaud, Bruce Reed, Star coloring of graphs Journal of Graph Theory. ,vol. 47, pp. 163- 182 ,(2004) , 10.1002/JGT.V47:3
Jaroslav Nešetřil, Patrice Ossona de Mendez, David R. Wood, Characterisations and examples of graph classes with bounded expansion The Journal of Combinatorics. ,vol. 33, pp. 350- 373 ,(2012) , 10.1016/J.EJC.2011.09.008
Xuding Zhu, Colouring graphs with bounded generalized colouring number Discrete Mathematics. ,vol. 309, pp. 5562- 5568 ,(2009) , 10.1016/J.DISC.2008.03.024
Daniel Lokshtanov, Dimitrios M. Thilikos, Saket Saurabh, Fedor V. Fomin, Linear kernels for (connected) dominating set on H-minor-free graphs symposium on discrete algorithms. pp. 82- 93 ,(2012) , 10.5555/2095116.2095123
Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, Dimitrios M. Thilikos, Meta) Kernelization foundations of computer science. pp. 629- 638 ,(2009) , 10.1109/FOCS.2009.46
Felix Reidl, Peter Rossmanith, Jarik Nešetril, Structural sparseness and complex networks Publikationsserver der RWTH Aachen University. ,(2016)
Rodney G. Downey, M. R. Fellows, Parameterized Complexity ,(1998)
Sebastian Ordyniak, Felix Reidl, Jakub Gajarský, Petr Hliněný, Peter Rossmanith, Jan Obdržálek, Somnath Sikdar, Fernando Sánchez Villaamil, Kernelization Using Structural Parameters on Sparse Graph Classes arXiv: Data Structures and Algorithms. ,(2013)