Wyszukiwarka
Abstrakt
A problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well as handle any vertex recoloring requests. Our main concern is the greedy approach and characterization of graph classes for which it is possible to decide in polynomial time whether for the fixed forbidden graph F and positive integer k the greedy algorithm ever uses more than k colors in dynamic F-free coloring. For various classes of graphs we give such characterizations in terms of a finite number of minimal forbidden graphs thus solving the above-mentioned problem for the so-called F-trees when F is 2-connected, and for classical trees, when F is a path of order 3 (the latter variant is also known as subcoloring or 1-improper coloring).
Cytowania
-
0
CrossRef
-
0
Web of Science
-
1
Scopus
Autorzy (2)
-
Elżbieta Sidorowicz
- Wydział Matematyki, Informatyki i Ekonometrii Zakłada matematyki Dyskretnej i Informatyki Teoretycznej
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00373-018-1886-8
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
GRAPHS AND COMBINATORICS
nr 34,
strony 457 - 475,
ISSN: 0911-0119 - Język:
- angielski
- Rok wydania:
- 2018
- Opis bibliograficzny:
- Borowiecki P., Sidorowicz E.: Dynamic F-free Coloring of Graphs// GRAPHS AND COMBINATORICS. -Vol. 34, nr. 3 (2018), s.457-475
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00373-018-1886-8
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 178 razy