Colouring and Covering Nowhere Dense Graphs

DOI10.1007/978-3-662-53174-7_23zbMath1417.05067arXiv1602.05926OpenAlexW2281443803MaRDI QIDQ2827820

Sebastian Siebertz, Roman Rabinovich, Stephan Kreutzer, Konstantinos S. Stavropoulos, Martin Grohe

Publication date: 21 October 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Density (toughness, etc.) (05C42)

Related Items (12)

Chromatic numbers of exact distance graphs ⋮ Edge degeneracy: algorithmic and structural results ⋮ A color-avoiding approach to subgraph counting in bounded expansion classes ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ On the Block Number of Graphs ⋮ Uniform orderings for generalized coloring numbers ⋮ On the weak 2-coloring number of planar graphs ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Unnamed Item ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ 2-coloring number revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Dense minors in graphs of large girth
• Strong-diameter decompositions of minor free graphs
• Colouring graphs with bounded generalized colouring number
• Orderings on graphs and game coloring number
• Constant-factor approximation of the domination number in sparse graphs
• On nowhere dense graphs
• Domination Problems in Nowhere-Dense Classes
• Approximate distance oracles
• A new series of dense graphs of high girth
• Distributed Computing: A Locality-Sensitive Approach
• Deciding First-Order Properties of Nowhere Dense Graphs
• Testing first-order properties for subclasses of sparse graphs

This page was built for publication: Colouring and Covering Nowhere Dense Graphs