Characterising bounded expansion by neighbourhood complexity

DOI10.1016/J.EJC.2018.08.001zbMATH Open1400.05248arXiv1603.09532OpenAlexW2963177880WikidataQ129194828 ScholiaQ129194828MaRDI QIDQ1621072FDOQ1621072

Authors: Felix Reidl, Fernando Sánchez Villaamil, Konstantinos S. Stavropoulos 

Publication date: 15 November 2018

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: We show that a graph class $calG$ has bounded expansion if and only if it has bounded $r$-neighbourhood complexity, i.e. for any vertex set $X$ of any subgraph $H$ of $GincalG$, the number of subsets of $X$ which are exact $r$-neighbourhoods of vertices of $H$ on $X$ is linear to the size of $X$. This is established by bounding the $r$-neighbourhood complexity of a graph in terms of both its $r$-centred colouring number and its weak $r$-colouring number, which provide known characterisations to the property of bounded expansion.

Full work available at URL: https://arxiv.org/abs/1603.09532

Recommendations

• Characterisations and examples of graph classes with bounded expansion
• Small graph classes and bounded expansion
• Grad and classes with bounded expansion. I: Decompositions
• Structural properties and constant factor-approximation of strong distance-\(r\) dominating sets in sparse directed graphs
• Grad and classes with bounded expansion. II: Algorithmic aspects

zbMATH Keywords

weak \(r\)-colouring number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (05C99)

Cites Work

• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Title not available (Why is that?)
• Characterisations and examples of graph classes with bounded expansion
• (Meta) Kernelization
• Bidimensionality and kernels
• Star coloring of graphs
• Sparsity. Graphs, structures, and algorithms
• Homomorphism preservation on quasi-wide classes
• Kernelization using structural parameters on sparse graph classes
• Deciding first-order properties of locally tree-decomposable structures
• Polynomial-time data reduction for dominating set
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• The structure of graphs not admitting a fixed immersion
• Mean, Median and Mode in Binomial Distributions
• Kernelization and Sparseness: the case of Dominating Set
• Graph minors. XVI: Excluding a non-planar graph
• Colouring graphs with bounded generalized colouring number
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fixed-parameter tractability, definability, and model-checking
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• Characterisations of nowhere dense graphs (invited talk)

Cited In (16)

• Structural properties and constant factor-approximation of strong distance-\(r\) dominating sets in sparse directed graphs
• Lossy kernels for connected dominating set on sparse graphs
• Characterisations and examples of graph classes with bounded expansion
• Title not available (Why is that?)
• Small graph classes and bounded expansion
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• Hardness of the generalized coloring numbers
• Algorithmic properties of sparse digraphs
• Bounding generalized coloring numbers of planar graphs using coin models
• Neighbourhood complexity of graphs of bounded twin-width
• Harmless sets in sparse classes
• On quasi-planar graphs: clique-width and logical description
• Bounds on half graph orders in powers of sparse graphs
• Hat Guessing Numbers of Strongly Degenerate Graphs
• Digraphs of bounded width
• Bounds on half graph orders in powers of sparse graphs

This page was built for publication: Characterising bounded expansion by neighbourhood complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1621072)