Characterising bounded expansion by neighbourhood complexity

DOI10.1016/j.ejc.2018.08.001zbMath1400.05248arXiv1603.09532OpenAlexW2963177880WikidataQ129194828 ScholiaQ129194828MaRDI QIDQ1621072

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

Publication date: 15 November 2018

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

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

zbMATH Keywords

weak \(r\)-colouring number

Mathematics Subject Classification ID

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

Related Items

Harmless sets in sparse classes, On quasi-planar graphs: clique-width and logical description, Neighbourhood complexity of graphs of bounded twin-width, Hat Guessing Numbers of Strongly Degenerate Graphs, Bounding generalized coloring numbers of planar graphs using coin models, Bounds on half graph orders in powers of sparse graphs, Unnamed Item, Unnamed Item, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness, Lossy Kernels for Connected Dominating Set on Sparse Graphs, Digraphs of Bounded Width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kernelization using structural parameters on sparse graph classes
• Sparsity. Graphs, structures, and algorithms
• The structure of graphs not admitting a fixed immersion
• Characterisations and examples of graph classes with bounded expansion
• Homomorphism preservation on quasi-wide classes
• Colouring graphs with bounded generalized colouring number
• Graph minors. XVI: Excluding a non-planar graph
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Fixed-Parameter Tractability, Definability, and Model-Checking
• Star coloring of graphs
• Deciding first-order properties of locally tree-decomposable structures
• Polynomial-time data reduction for dominating set
• Mean, Median and Mode in Binomial Distributions
• Kernelization and Sparseness: the case of Dominating Set
• Deciding First-Order Properties of Nowhere Dense Graphs
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• (Meta) Kernelization
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• Bidimensionality and Geometric Graphs