Discussiones Mathematicae Graph Theory 26(3) (2006) 389-401
doi: 10.7151/dmgt.1331

[BIBTex] [PDF] [PS]

ON-LINE P-COLORING OF GRAPHS

Piotr Borowiecki

Faculty of Mathematics, Computer Science
and Econometrics, University of Zielona Góra
Prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland
e-mail: P.Borowiecki@wmie.uz.zgora.pl

Abstract

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.

Keywords: on-line algorithm, graph coloring, hereditary property.

2000 Mathematics Subject Classification: 05C15, 05C85, 68R10.

References

[1] D.R. Bean, Effective coloration, J. Symbolic Logic 41 (1976) 469-480, doi: 10.2307/2272247.
[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.
[3] P. Borowiecki, On-line coloring of graphs, in: M. Kubale ed., Graph Colorings, Contemporary Mathematics 352 (American Mathematical Society, 2004) 21-33.
[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.
[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.

Received 12 January 2006
Revised 24 October 2006