Improved bounds for centered colorings

DOI10.19086/AIC.27351zbMATH Open1478.05050arXiv1907.04586OpenAlexW2958527737MaRDI QIDQ5162872FDOQ5162872

Authors: Michał Dębski, Stefan Felsner, Piotr Micek, Felix Schröder 

Publication date: 5 November 2021

Published in: Advances in Combinatorics (Search for Journal in Brave)

Abstract: A vertex coloring $phi$ of a graph $G$ is $p$-centered if for every connected subgraph $H$ of $G$ either $phi$ uses more than $p$ colors on $H$ or there is a color that appears exactly once on $H$. Centered colorings form one of the families of parameters that allow to capture notions of sparsity of graphs: A class of graphs has bounded expansion if and only if there is a function $f$ such that for every $pgeq1$, every graph in the class admits a $p$-centered coloring using at most $f(p)$ colors. In this paper, we give upper bounds for the maximum number of colors needed in a $p$-centered coloring of graphs from several widely studied graph classes. We show that: (1) planar graphs admit $p$-centered colorings with $mathcalO(p^{3}logp)$ colors where the previous bound was $mathcalO(p^{19})$; (2) bounded degree graphs admit $p$-centered colorings with $mathcalO(p)$ colors while it was conjectured that they may require exponential number of colors in $p$; (3) graphs avoiding a fixed graph as a topological minor admit $p$-centered colorings with a polynomial in $p$ number of colors. All these upper bounds imply polynomial algorithms for computing the colorings. Prior to this work there were no non-trivial lower bounds known. We show that: (4) there are graphs of treewidth $t$ that require $$ colors in any $p$-centered coloring and this bound matches the upper bound; (5) there are planar graphs that require $Omega(p^{2}logp)$ colors in any $p$-centered coloring.

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

Recommendations

• Two lower bounds for \(p\)-centered colorings
• Colouring graphs with bounded generalized colouring number
• Bounds on vertex colorings with restrictions on the union of color classes

zbMATH Keywords

vertex coloring\(p\)-centered coloringa class of graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Grad and classes with bounded expansion. I: Decompositions
• Tree-depth, subgraph coloring and homomorphism bounds
• New approach to nonrepetitive sequences
• Characterisations and examples of graph classes with bounded expansion
• Star coloring of graphs
• Layout of Graphs with Bounded Tree-Width
• A constructive proof of the general Lovász local lemma
• On nowhere dense graphs
• Graph minors. XVI: Excluding a non-planar graph
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• Nonrepetitive colorings of graphs of bounded tree-width
• Testing first-order properties for subclasses of sparse graphs
• On space efficiency of algorithms working on structural decompositions of graphs
• Improved bounds for centered colorings
• A fast algorithm for the product structure of planar graphs
• Two lower bounds for \(p\)-centered colorings
• Planar graphs have bounded queue-number
• Polynomial treedepth bounds in linear colorings

Cited In (15)

• Separating layered treewidth and row treewidth
• The product structure of squaregraphs
• Improved bounds for weak coloring numbers
• Bounded-degree planar graphs do not have bounded-degree product structure
• Graph product structure for non-minor-closed classes
• Improved product structure for graphs on surfaces
• An improved planar graph product structure theorem
• Product structure of graph classes with bounded treewidth
• A \(p\)-centered coloring for the grid using \(O(p)\) colors
• Graph colorings with restricted bicolored subgraphs: I. Acyclic, star, and treewidth colorings
• A general framework for hypergraph coloring
• Two lower bounds for \(p\)-centered colorings
• Product structure of graphs with an excluded minor
• Graph product structure for \(h\)-framed graphs
• Shallow Minors, Graph Products, and Beyond-Planar Graphs

This page was built for publication: Improved bounds for centered colorings

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