- Tytuł:
- On-line -coloring of graphs
- Autorzy:
- Borowiecki, Piotr
- Powiązania:
- https://bibliotekanauki.pl/articles/743585.pdf
- Data publikacji:
- 2006
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
on-line algorithm
graph coloring
hereditary property - Opis:
- For a given induced hereditary property , a -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 . We consider the effectiveness of on-line -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 -coloring algorithm. In the class of generalized trees, we characterize graphs critical for the greedy -coloring. A class of graphs for which a greedy algorithm always generates optimal -colorings for the property = K₃-free is given.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2006, 26, 3; 389-401
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł