Two lower bounds for p-centered colorings

DOI10.23638/DMTCS-22-4-9MaRDI QIDQ3386629zbMATHFDO

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

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

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

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.

Recommendations

• Improved bounds for centered colorings
• Chromatic numbers of exact distance graphs
• Colouring graphs with bounded generalized colouring number

Cites work

• Acyclic coloring of graphs
• Approximation algorithms for polynomial-expansion and low-density graphs
• Coloring and covering nowhere dense graphs
• Grad and classes with bounded expansion. I: Decompositions
• Improved bounds for centered colorings
• Introduction to Random Graphs
• Sparsity. Graphs, structures, and algorithms
• Star coloring of graphs
• Strongly sublinear separators and polynomial expansion
• The probabilistic method

Cited in

(7)

• Treedepth bounds in linear colorings
• Notes on graph product structure theory
• Separating layered treewidth and row treewidth
• Improved bounds for weak coloring numbers
• Bounds on half graph orders in powers of sparse graphs
• Improved bounds for centered colorings
• A \(p\)-centered coloring for the grid using \(O(p)\) colors

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)