Coloring and Covering Nowhere Dense Graphs

DOI10.1137/18M1168753zbMath1398.05121OpenAlexW2898841741WikidataQ129020508 ScholiaQ129020508MaRDI QIDQ4553722

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

Publication date: 31 October 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/18m1168753

zbMATH Keywords

nowhere dense graphsgeneralized coloring numbersneighborhood covers

Mathematics Subject Classification ID

Applications of graph theory (05C90) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Density (toughness, etc.) (05C42)

Related Items (12)

Improved bounds for weak coloring numbers ⋮ On coloring numbers of graph powers ⋮ Separating layered treewidth and row treewidth ⋮ Two lower bounds for $p$-centered colorings ⋮ On weighted sublinear separators ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Uniform orderings for generalized coloring numbers ⋮ Polynomial bounds for centered colorings on proper minor-closed graph classes ⋮ Notes on graph product structure theory ⋮ Twin-width and generalized coloring numbers

Cites Work

• Dense minors in graphs of large girth
• Strong-diameter decompositions of minor free graphs
• On low tree-depth decompositions
• Colouring graphs with bounded generalized colouring number
• Polynomial expansion and sublinear separators
• 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
• Radius two trees specify χ‐bounded classes
• A new series of dense graphs of high girth
• Distributed Computing: A Locality-Sensitive Approach
• Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
• Deciding First-Order Properties of Nowhere Dense Graphs
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• Testing first-order properties for subclasses of sparse graphs
• On the generalised colouring numbers of graphs that exclude a fixed minor
• Unnamed Item
• Unnamed Item
• Unnamed Item

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