{
  "id": "2006.04113",
  "version": "v1",
  "published": "2020-06-07T11:02:41.000Z",
  "updated": "2020-06-07T11:02:41.000Z",
  "title": "Two lower bounds for $p$-centered colorings",
  "authors": [
    "Loïc Dubois",
    "Gwenaël Joret",
    "Guillem Perarnau",
    "Marcin Pilipczuk",
    "François Pitois"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Given a graph $G$ and an integer $p$, a coloring $f : V(G) \\to \\mathbb{N}$ is $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}\\'ak and Norin), admitting strongly sublinear separators. We construct such a class such that $p$-centered colorings require a number of colors exponential 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\\\"{o}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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-06-07T11:02:41.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "lower bounds",
      "maximum degree",
      "polynomial upper bound",
      "shallow minors",
      "average degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}