Characterising Bounded Expansion by Neighbourhood Complexity

We show that a graph class $\cal G$ 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 $G\in\cal G$, 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.

• Publication year

  2016

• Venue

  European journal of combinatorics (Print)

• Publication date

  2016-03-31

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/J.EJC.2018.08.001arXiv 1603.09532
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Structural sparseness and complex networks

  2016cited by this paper
• Kernelization and Sparseness: the case of Dominating Set

  2014cited by this paper
• Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs

  2014cited by this paper
• The structure of graphs not admitting a fixed immersion

  2013cited by this paper
• Deciding first-order properties of nowhere dense graphs

  2013cited by this paper
• Kernelization Using Structural Parameters on Sparse Graph Classes

  2013cited by this paper
• Characterisations of Nowhere Dense Graphs

  2013cited by this paper
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions

  2012cited by this paper
• Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs

  2012cited by this paper
• Linear kernels for (connected) dominating set on H-minor-free graphs

  2012cited by this paper
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs

  2011cited by this paper
• Bidimensionality and kernels

  2010cited by this paper
• Deciding First-Order Properties for Sparse Graphs

  2010cited by this paper
• Decomposition, approximation, and coloring of odd-minor-free graphs

  2010cited by this paper
• Colouring graphs with bounded generalized colouring number

  2009cited by this paper
• Characterisations and examples of graph classes with bounded expansion

  2009cited by this paper
• (Meta) Kernelization

  2009cited by this paper
• Homomorphism Preservation on Quasi-Wide Classes

  2008cited by this paper
• Locally Excluding a Minor

  2007cited by this paper
• Asymptotical Structure of Combinatorial Objects

  2007cited by this paper
• Grad and classes with bounded expansion I. Decompositions

  2005influential reference
• Grad and classes with bounded expansion II. Algorithmic aspects

  2005cited by this paper
• Star coloring of graphs

  2004cited by this paper
• Graph Minors. XVI. Excluding a non-planar graph

  2003cited by this paper
• Polynomial-time data reduction for dominating set

  2002cited by this paper
• Deciding first-order properties of locally tree-decomposable structures

  2000cited by this paper
• Fixed-Parameter Tractability, Definability, and Model-Checking

  1999cited by this paper
• Parameterized Complexity

  1998cited by this paper
• Linear time computable problems and first-order descriptions

  1996cited by this paper
• Mean, Median and Mode in Binomial Distributions

  1980cited by this paper

• On the generalized coloring numbers

  2026cites this paper
• Near-Linear Time Computation of Welzl Orders on Graphs with Linear Neighborhood Complexity

  2026cites this paper
• Flips and Merge-Width in Sparse Graphs

  2026cites this paper
• Classification of polyhedral graphs by numbers of common neighbours

  2025cites this paper
• Efficiently Finding and Counting Patterns with Distance Constraints in Sparse Graphs

  2025cites this paper
• Odd coloring graphs with linear neighborhood complexity

  2025cites this paper
• Girth in $GF(q)$-representable matroids

  2025cites this paper
• Pushing the frontiers of subexponential FPT time for Feedback Vertex Set

  2025cites this paper
• χ-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs

  2025cites this paper
• Girth in GF(q)$\textsf {GF}(q)$ ‐representable matroids

  2025cites this paper
• A sufficient condition for characterizing the one-sided testable properties of families of graphs in the Random Neighbour Oracle Model

  2025cites this paper
• Adjacency Labeling Schemes for Small Classes

  2024cites this paper
• Neighborhood Complexity of Planar Graphs

  2023influential citation
• Subexponential Algorithms in Geometric Graphs via the Subquadratic Grid Minor Property: The Role of Local Radius

  2023cites this paper
• Fully dynamic approximation schemes on planar and apex-minor-free graphs

  2023cites this paper
• Cop-width, flip-width and strong colouring numbers

  2023cites this paper
• Efficient Approximation for Subgraph-Hitting Problems in Sparse Graphs and Geometric Intersection Graphs

  2023cites this paper
• Subexponential parameterized algorithms for cycle-hitting problems in contact and intersection graphs of segments

  2023influential citation
• Neighbourhood complexity of graphs of bounded twin-width

  2023cites this paper
• Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)

  2022cites this paper
• Bounding generalized coloring numbers of planar graphs using coin models

  2022cites this paper
• VC-density and abstract cell decomposition for edge relation in graphs of bounded twin-width

  2022cites this paper
• Turbocharging Heuristics for Weak Coloring Numbers

  2022cites this paper
• Distal Combinatorial Tools for Graphs of Bounded Twin-Width

  2022cites this paper
• Hat Guessing Numbers of Strongly Degenerate Graphs

  2021cites this paper
• Hardness of the Generalized Coloring Numbers

  2021cites this paper
• Kernelization and hardness of harmless sets in sparse classes

  2021cites this paper
• Harmless Sets in Sparse Classes

  2021cites this paper
• Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes

  2021cites this paper
• First-Order Transductions of Graphs

  2021cites this paper
• Bounds on half graph orders in powers of sparse graphs

  2021cites this paper
• Approximation Metatheorems for Classes with Bounded Expansion

  2021cites this paper
• A general kernelization technique for domination and independence problems in sparse classes

  2020cites this paper
• Digraphs of Bounded Width

  2018cites this paper
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness

  2018cites this paper
• Lossy kernels for connected distance-$r$ domination on nowhere dense graph classes

  2017cites this paper
• Lossy Kernels for Connected Dominating Set on Sparse Graphs

  2017influential citation
• Experimental Evaluation of Counting Subgraph Isomorphisms in Classes of Bounded Expansion

  2017cites this paper
• On quasi-planar graphs: Clique-width and logical description

  2017cites this paper
• Chromatic and structural properties of sparse graph classes

  2017cites this paper
• Algorithmic Properties of Sparse Digraphs

  2017cites this paper
• On the number of types in sparse graphs

  2017influential citation
• Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs

  2017cites this paper
• An Experimental Evaluation of a Bounded Expansion Algorithmic Pipeline

  2017cites this paper
• Neighborhood complexity and kernelization for nowhere dense classes of graphs

  2016influential citation
• Subexponential parameterized algorithms in square graphs and intersection graphs of thin objects

  year unknowncites this paper
• European Journal of Combinatorics

  year unknowncites this paper