Improved bounds for centered colorings

D 2020

Improved bounds for centered colorings

DĘBSKI, Michał Karol; Stefan FELSNER; Piotr MICEK a Felix SCHRÖDER

Základní údaje

Originální název

Improved bounds for centered colorings

Autoři

DĘBSKI, Michał Karol; Stefan FELSNER; Piotr MICEK a Felix SCHRÖDER

Vydání

Not specified, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, od s. 2212-2226, 15 s. 2020

Nakladatel

SIAM

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Kód RIV

RIV/00216224:14330/20:00115527

Organizační jednotka

Fakulta informatiky

ISBN

978-1-61197-599-4

DOI

https://doi.org/10.1137/1.9781611975994.136

UT WoS

000554408102017

EID Scopus

2-s2.0-85084076155

Klíčová slova anglicky

centered coloring; bounded expansion; planar graph; entropy compression

Štítky

core_A, firank_1

Změněno: 14. 6. 2022 13:54, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

A vertex coloring c of a graph G is p-centered if for every connected subgraph H of G either c 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(p^3 log p) colors where the previous bound was O(p^19); (2) bounded degree graphs admit p-centered colorings with O(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 (p+t choose t) colors in any p-centered coloring and this bound matches the upper bound; (5) there are planar graphs that require Omega(p^2 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 with various proof 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ávaznosti

EF16_027/0008360, projekt VaV

Název: Postdoc@MUNI

Citovat

DĘBSKI, Michał Karol; Stefan FELSNER; Piotr MICEK a Felix SCHRÖDER. Improved bounds for centered colorings. Online. In Shuchi Chawla. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms. Not specified: SIAM, 2020, s. 2212-2226. ISBN 978-1-61197-599-4. Dostupné z: https://doi.org/10.1137/1.9781611975994.136.

@inproceedings{1645722,
   author = {Dębski, Michał Karol and Felsner, Stefan and Micek, Piotr and Schröder, Felix},
   address = {Not specified},
   booktitle = {Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms},
   doi = {https://doi.org/10.1137/1.9781611975994.136},
   editor = {Shuchi Chawla},
   keywords = {centered coloring; bounded expansion; planar graph; entropy compression},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Not specified},
   isbn = {978-1-61197-599-4},
   pages = {2212-2226},
   publisher = {SIAM},
   title = {Improved bounds for centered colorings},
   url = {https://epubs.siam.org/doi/abs/10.1137/1.9781611975994.136},
   year = {2020}
}

TY  - CONF
ID  - 1645722
AU  - Dębski, Michał Karol - Felsner, Stefan - Micek, Piotr - Schröder, Felix
PY  - 2020
TI  - Improved bounds for centered colorings
PB  - SIAM
CY  - Not specified
SN  - 9781611975994
KW  - centered coloring
KW  - bounded expansion
KW  - planar graph
KW  - entropy compression
UR  - https://epubs.siam.org/doi/abs/10.1137/1.9781611975994.136
L2  - https://epubs.siam.org/doi/abs/10.1137/1.9781611975994.136
N2  - A vertex coloring c of a graph G is p-centered if for every connected subgraph H of G either c 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(p^3 log p) colors where the previous bound was O(p^19); (2) bounded degree graphs admit p-centered colorings with O(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 (p+t choose t) colors in any p-centered coloring and this bound matches the upper bound; (5) there are planar graphs that require Omega(p^2 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 with various proof 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.
ER  -

DĘBSKI, Michał Karol; Stefan FELSNER; Piotr MICEK a Felix SCHRÖDER. Improved bounds for centered colorings. Online. In Shuchi Chawla. \textit{Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms}. Not specified: SIAM, 2020, s.~2212-2226. ISBN~978-1-61197-599-4. Dostupné z: https://doi.org/10.1137/1.9781611975994.136.

Přehled o publikaci