Wyszukiwarka
Abstrakt
For a given induced hereditary property P, a P-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property P. We consider the effectiveness of on-line P-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function of any stingy on-line P-coloring algorithm. In the class of generalized trees, we characterize graphs critical for the greedy P-coloring. A class of graphs for which a greedy algorithm always generates optimal P-colorings for the property P = K3-free is given.
Cytowania
-
2
CrossRef
-
0
Web of Science
-
0
Scopus
Cytuj jako
Pełna treść
pobierz publikację
pobrano 25 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.1331
- 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:
-
Discussiones Mathematicae Graph Theory
nr 26,
wydanie 3,
strony 389 - 401,
ISSN: 1234-3099 - Język:
- angielski
- Rok wydania:
- 2006
- Opis bibliograficzny:
- Borowiecki P.: On-line P-coloring of graphs// Discussiones Mathematicae Graph Theory. -Vol. 26, iss. 3 (2006), s.389-401
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.1331
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 117 razy