Acyclic, star and injective colouring: A complexity picture for H-free graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10515256" target="_blank" >RIV/00216208:11320/25:10515256 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=mMWykZ3uZI" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=mMWykZ3uZI</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jcss.2025.103662" target="_blank" >10.1016/j.jcss.2025.103662</a>

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 (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are ACYCLIC COLOURING, STAR COLOURING and INJECTIVE COLOURING. We give almost complete complexity classifications for ACYCLIC COLOURING, STAR COLOURING and INJECTIVE COLOURING on H-free graphs (for each of the problems, we have one open case). Moreover, we give full complexity classifications if the number of colours k is fixed, that is, not part of the input. From our study it follows 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 of multigraphs.

Název v anglickém jazyce

Acyclic, star and injective colouring: A complexity picture for H-free graphs

Popis výsledku anglicky

A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are ACYCLIC COLOURING, STAR COLOURING and INJECTIVE COLOURING. We give almost complete complexity classifications for ACYCLIC COLOURING, STAR COLOURING and INJECTIVE COLOURING on H-free graphs (for each of the problems, we have one open case). Moreover, we give full complexity classifications if the number of colours k is fixed, that is, not part of the input. From our study it follows 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 of multigraphs.

Druh

J_imp - Článek v periodiku v databázi Web of Science

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

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

Rok uplatnění

2025

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

Journal of Computer and System Sciences

ISSN

0022-0000

e-ISSN

1090-2724

Svazek periodika

154

Číslo periodika v rámci svazku

December 2025

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

18

Strana od-do

103662

Kód UT WoS článku

001492605500001

EID výsledku v databázi Scopus

2-s2.0-105004878641