Improved bounds for centered colorings

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Improved bounds for centered colorings

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Improved bounds for centered colorings

Popis výsledku anglicky

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.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

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

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2021

Kód důvěrnosti údajů

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

Název periodika

Advances in Combinatorics

ISSN

2517-5599

e-ISSN

—

Svazek periodika

2021

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

28

Strana od-do

1-28

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85115731316