Geodesic
On-line -coloring of graphs
Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 3, pp. 389-401

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: on-line algorithm, graph coloring, hereditary property 
@article{DMGT_2006_26_3_a3,
     author = {Borowiecki, Piotr},
     title = {On-line -coloring of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {389--401},
     publisher = {mathdoc},
     volume = {26},
     number = {3},
     year = {2006},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2006_26_3_a3/}
}
TY  - JOUR
AU  - Borowiecki, Piotr
TI  - On-line -coloring of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2006
SP  - 389
EP  - 401
VL  - 26
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2006_26_3_a3/
LA  - en
ID  - DMGT_2006_26_3_a3
ER  - 
%0 Journal Article
%A Borowiecki, Piotr
%T On-line -coloring of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2006
%P 389-401
%V 26
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2006_26_3_a3/
%G en
%F DMGT_2006_26_3_a3
Borowiecki, Piotr. On-line -coloring of graphs. Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 3, pp. 389-401. http://geodesic.mathdoc.fr/item/DMGT_2006_26_3_a3/