PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wynik贸w
2006 | 26 | 3 | 389-401
Tytu艂 artyku艂u

On-line 饾摕-coloring of graphs

Tre艣膰 / Zawarto艣膰
Warianty tytu艂u
J臋zyki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
26
Numer
3
Strony
389-401
Opis fizyczny
Daty
wydano
2006
otrzymano
2006-01-12
poprawiono
2006-10-24
Tw贸rcy
  • Faculty of Mathematics, Computer Science, and Econometrics, University of Zielona G贸ra, Prof. Z. Szafrana 4a, 65-516 Zielona G贸ra, Poland
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1331
JavaScript jest wy艂膮czony w Twojej przegl膮darce internetowej. W艂膮cz go, a nast臋pnie od艣wie偶 stron臋, aby m贸c w pe艂ni z niej korzysta膰.