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
topHow 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.