Loïc Dubois ; Gwenaël Joret ; Guillem Perarnau ; Marcin Pilipczuk ; François Pitois - Two lower bounds for $p$-centered colorings

dmtcs:6543 - Discrete Mathematics & Theoretical Computer Science, November 11, 2020, vol. 22 no. 4 - https://doi.org/10.23638/DMTCS-22-4-9
Two lower bounds for $p$-centered coloringsArticle

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

    Given a graph $G$ and an integer $p$, a coloring $f : V(G) \to \mathbb{N}$ 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 Dvo\v{r}ák 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$. D\k{e}bski, Felsner, Micek, and Schröder recently proved that these graphs have $p$-centered colorings with $O(\Delta^{2-1/p} p)$ colors. We show that there are graphs of maximum degree $\Delta$ that require $\Omega(\Delta^{2-1/p} p \ln^{-1/p}\Delta)$ colors in any $p$-centered coloring, thus matching their upper bound up to a logarithmic factor.


    Volume: vol. 22 no. 4
    Section: Graph Theory
    Published on: November 11, 2020
    Accepted on: October 15, 2020
    Submitted on: June 9, 2020
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics
    Funding:
      Source : OpenAIRE Graph
    • Cuts and decompositions: algorithms and combinatorial properties; Funder: European Commission; Code: 714704

    Consultation statistics

    This page has been seen 640 times.
    This article's PDF has been downloaded 291 times.