On-line 𝓟-coloring of graphs
Piotr Borowiecki
Discussiones Mathematicae Graph Theory, Tome 26 (2006), p. 389-401 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2006-01-01
EUDML-ID : urn:eudml:doc:270708 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1331,
     author = {Piotr Borowiecki},
     title = {On-line P-coloring of graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {26},
     year = {2006},
     pages = {389-401},
     zbl = {1138.05019},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1331}
}

Piotr Borowiecki. On-line 𝓟-coloring of graphs. Discussiones Mathematicae Graph Theory, Tome 26 (2006) pp. 389-401. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1331/

[000] [1] D.R. Bean, Effective coloration, J. Symbolic Logic 41 (1976) 469-480, doi: 10.2307/2272247. | Zbl 0331.02025

[001] [2] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. | Zbl 0902.05026

[002] [3] P. Borowiecki, On-line coloring of graphs, in: M. Kubale ed., Graph Colorings, Contemporary Mathematics 352 (American Mathematical Society, 2004) 21-33.

[003] [4] A. Gyárfás and J. Lehel, First-Fit and on-line chromatic number of families of graphs, Ars Combinatoria 29C (1990) 168-176. | Zbl 0712.05026

[004] [5] H.A. Kierstead, Coloring Graphs On-line, in: A. Fiat and G.J. Woeginger eds., Online Algorithms - The State of the Art, LNCS 1442 (Springer, Berlin, 1998) 281-305.