All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Improved bounds for centered colorings

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F20%3A00115527" target="_blank" >RIV/00216224:14330/20:00115527 - isvavai.cz</a>

  • Result on the web

    <a href="https://epubs.siam.org/doi/abs/10.1137/1.9781611975994.136" target="_blank" >https://epubs.siam.org/doi/abs/10.1137/1.9781611975994.136</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1137/1.9781611975994.136" target="_blank" >10.1137/1.9781611975994.136</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    Improved bounds for centered colorings

  • Original language description

    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 &gt;= 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.

  • Czech name

  • Czech description

Classification

  • Type

    D - Article in proceedings

  • CEP classification

  • OECD FORD branch

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

Result continuities

  • Project

    <a href="/en/project/EF16_027%2F0008360" target="_blank" >EF16_027/0008360: Postdoc@MUNI</a><br>

  • Continuities

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Others

  • Publication year

    2020

  • Confidentiality

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

Data specific for result type

  • Article name in the collection

    Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms

  • ISBN

    9781611975994

  • ISSN

  • e-ISSN

  • Number of pages

    15

  • Pages from-to

    2212-2226

  • Publisher name

    SIAM

  • Place of publication

    Not specified

  • Event location

    Salt Lake City

  • Event date

    Jan 1, 2020

  • Type of event by nationality

    WRD - Celosvětová akce

  • UT code for WoS article

    000554408102017