Two lower bounds for $p$-centered colorings

DOI10.23638/DMTCS-22-4-9zbMath1477.05074arXiv2006.04113MaRDI QIDQ3386629

Marcin Pilipczuk, Guillem Perarnau, François Pitois, Loïc Dubois, Gwenaël Joret

Publication date: 5 January 2021

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

zbMATH Keywords

polynomial expansionbounded expansion\(p\)-centered coloring

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)

Related Items (5)

Improved bounds for weak coloring numbers ⋮ Separating layered treewidth and row treewidth ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Improved Bounds for Centered Colorings ⋮ Notes on graph product structure theory

Cites Work

• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Polynomial bounds for centered colorings on proper minor-closed graph classes
• Grad and classes with bounded expansion. I: Decompositions
• Strongly Sublinear Separators and Polynomial Expansion
• Introduction to Random Graphs
• Star coloring of graphs
• Acyclic coloring of graphs
• Coloring and Covering Nowhere Dense Graphs
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Improved bounds for centered colorings

This page was built for publication: Two lower bounds for $p$-centered colorings