# On-line 𝓟-coloring of graphs

Discussiones Mathematicae Graph Theory (2006)

- Volume: 26, Issue: 3, page 389-401
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topPiotr Borowiecki. "On-line 𝓟-coloring of graphs." Discussiones Mathematicae Graph Theory 26.3 (2006): 389-401. <http://eudml.org/doc/270708>.

@article{PiotrBorowiecki2006,

abstract = {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.},

author = {Piotr Borowiecki},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {on-line algorithm; graph coloring; hereditary property; greedy algorithm; graph colouring; stingy algorithm},

language = {eng},

number = {3},

pages = {389-401},

title = {On-line 𝓟-coloring of graphs},

url = {http://eudml.org/doc/270708},

volume = {26},

year = {2006},

}

TY - JOUR

AU - Piotr Borowiecki

TI - On-line 𝓟-coloring of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2006

VL - 26

IS - 3

SP - 389

EP - 401

AB - 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.

LA - eng

KW - on-line algorithm; graph coloring; hereditary property; greedy algorithm; graph colouring; stingy algorithm

UR - http://eudml.org/doc/270708

ER -

## References

top- [1] D.R. Bean, Effective coloration, J. Symbolic Logic 41 (1976) 469-480, doi: 10.2307/2272247. Zbl0331.02025
- [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. Zbl0902.05026
- [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. Zbl0712.05026
- [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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.