Two lower bounds for p-centered colorings

DOI10.23638/DMTCS-22-4-9zbMATH Open1477.05074arXiv2006.04113MaRDI QIDQ3386629FDOQ3386629

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

Publication date: 5 January 2021

Abstract: Given a graph $G$ and an integer $p$, a coloring $f:V(G)omathbbN$ is emph{$p$-centered} if for every connected subgraph $H$ of $G$, either $f$ uses more than $p$ colors on $H$ or there is a color that appears exactly once in $H$. The notion of $p$-centered colorings plays a central role in the theory of sparse graphs. In this note we show two lower bounds on the number of colors required in a $p$-centered coloring. First, we consider monotone classes of graphs whose shallow minors have average degree bounded polynomially in the radius, or equivalently (by a result of Dvov{r}'ak and Norin), admitting strongly sublinear separators. We construct such a class such that $p$-centered colorings require a number of colors super-polynomial in $p$. This is in contrast with a recent result of Pilipczuk and Siebertz, who established a polynomial upper bound in the special case of graphs excluding a fixed minor. Second, we consider graphs of maximum degree $Delta$. Dk{e}bski, Felsner, Micek, and Schr"{o}der recently proved that these graphs have $p$-centered colorings with $O(Delt{a}^{2-1/p}p)$ colors. We show that there are graphs of maximum degree $Delta$ that require $Omega(Delt{a}^{2-1/p}pl{n}^{-1/p}Delta)$ colors in any $p$-centered coloring, thus matching their upper bound up to a logarithmic factor.

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

zbMATH Keywords

polynomial expansionbounded expansion\(p\)-centered coloring

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386629)