Improved bounds for centered colorings

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F21%3A00136005" target="_blank" >RIV/00216224:14330/21:00136005 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.19086/aic.27351" target="_blank" >https://doi.org/10.19086/aic.27351</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.19086/aic.27351" target="_blank" >10.19086/aic.27351</a>

Result language

angličtina

Original language name

Improved bounds for centered colorings

Original language description

A vertex coloring φ of a graph G is p-centered if for every connected subgraph H of G either φ 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 p ≥ 1, 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 O(p3 log p) colors where the previous bound was O(p19 ); (2) bounded degree graphs admit p-centered colorings with O(p) colors while it was conjectured that they require an 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( ) p+t t colors in any p-centered coloring; this matches the known upper bound. (5) there are planar graphs that require Ω(p2 log p) colors in any p-centered coloring. We also give asymptotically tight bounds for outerplanar graphs and planar graphs of treewidth 3. We prove our results using a variety of techniques. The upper bound for planar graphs involves an application of a recent structure theorem while the upper bound for bounded degree graphs comes from the entropy compression method. We lift the result for bounded degree graphs to graphs avoiding a fixed topological minor using the Grohe–Marx structure theorem.

Czech name

—

Czech description

—

Type

J_SC - Article in a specialist periodical, which is included in the SCOPUS database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2021

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Advances in Combinatorics

ISSN

2517-5599

e-ISSN

—

Volume of the periodical

2021

Issue of the periodical within the volume

1

Country of publishing house

GB - UNITED KINGDOM

Number of pages

28

Pages from-to

1-28

UT code for WoS article

—

EID of the result in the Scopus database

2-s2.0-85115731316