Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10422003" target="_blank" >RIV/00216208:11320/20:10422003 - isvavai.cz</a>

  • Výsledek na webu

    <a href="https://doi.org/10.4230/LIPIcs.ESA.2020.22" target="_blank" >https://doi.org/10.4230/LIPIcs.ESA.2020.22</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.4230/LIPIcs.ESA.2020.22" target="_blank" >10.4230/LIPIcs.ESA.2020.22</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs

  • Popis výsledku v původním jazyce

    A k-colouring c of a graph G is a mapping V(G) RIGHTWARDS ARROW {1,2,... k} such that c(u) NOT EQUAL TO c(v) whenever u and v are adjacent. The corresponding decision problem is Colouring. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. Hence, every injective colouring is a star colouring and every star colouring is an acyclic colouring. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring (the last problem is also known as L(1,1)-Labelling). A classical complexity result on Colouring is a well-known dichotomy for H-free graphs, which was established twenty years ago (in this context, a graph is H-free if and only if it does not contain H as an induced subgraph). Moreover, this result has led to a large collection of results, which helped us to better understand the complexity of Colouring. In contrast, there is no systematic study into the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring despite numerous algorithmic and structural results that have appeared over the years. We initiate such a systematic complexity study, and similar to the study of Colouring we use the class of H-free graphs as a testbed. We prove the following results: 1) We give almost complete classifications for the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring for H-free graphs. 2) If the number of colours k is fixed, that is, not part of the input, we give full complexity classifications for each of the three problems for H-free graphs. From our study we conclude that for fixed k the three problems behave in the same way, but this is no longer true if k is part of the input. To obtain several of our results we prove stronger complexity results that in particular involve the girth of a graph and the class of line graphs.

  • Název v anglickém jazyce

    Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs

  • Popis výsledku anglicky

    A k-colouring c of a graph G is a mapping V(G) RIGHTWARDS ARROW {1,2,... k} such that c(u) NOT EQUAL TO c(v) whenever u and v are adjacent. The corresponding decision problem is Colouring. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. Hence, every injective colouring is a star colouring and every star colouring is an acyclic colouring. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring (the last problem is also known as L(1,1)-Labelling). A classical complexity result on Colouring is a well-known dichotomy for H-free graphs, which was established twenty years ago (in this context, a graph is H-free if and only if it does not contain H as an induced subgraph). Moreover, this result has led to a large collection of results, which helped us to better understand the complexity of Colouring. In contrast, there is no systematic study into the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring despite numerous algorithmic and structural results that have appeared over the years. We initiate such a systematic complexity study, and similar to the study of Colouring we use the class of H-free graphs as a testbed. We prove the following results: 1) We give almost complete classifications for the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring for H-free graphs. 2) If the number of colours k is fixed, that is, not part of the input, we give full complexity classifications for each of the three problems for H-free graphs. From our study we conclude that for fixed k the three problems behave in the same way, but this is no longer true if k is part of the input. To obtain several of our results we prove stronger complexity results that in particular involve the girth of a graph and the class of line graphs.

Klasifikace

  • Druh

    D - Stať ve sborníku

  • CEP obor

  • OECD FORD obor

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

Návaznosti výsledku

  • Projekt

  • Návaznosti

    S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Ostatní

  • Rok uplatnění

    2020

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

Údaje specifické pro druh výsledku

  • Název statě ve sborníku

    28th Annual European Symposium on Algorithms (ESA 2020)

  • ISBN

    978-3-95977-162-7

  • ISSN

    1868-8969

  • e-ISSN

  • Počet stran výsledku

    22

  • Strana od-do

    1-22

  • Název nakladatele

    Leibniz International Proceedings in Informatics (LIPIcs)

  • Místo vydání

    Dagstuhl, Německo

  • Místo konání akce

    online

  • Datum konání akce

    7. 9. 2020

  • Typ akce podle státní příslušnosti

    WRD - Celosvětová akce

  • Kód UT WoS článku