A survey of hard-to-color graphs for off-line and on-line model of vertex coloring

• Autorzy: Borowiecki, P. , Kubale, M.
• Języki publikacji: EN

Abstrakty

EN

In the paper we review the most popular on-line and off-line graph coloring algorithms. For each algorithm we give: short description. performance guarantee, the smallest HC and slightly HC graphs, positive cases and negative cases. Finally, we give the smallest benchmark for off-line sequential algorithms and the smallest weak benchmark for on-line algorithms.

Słowa kluczowe

PL

kolorowanie grafów; graf trudny do kolorowania; algorytm online; algorytm offline; kolorowanie wierzchołków

EN

graph coloring; hard-to-color graph; on-line algorithm; off-line algorithm; vertex coloring

• Czasopismo: Journal of Applied Computer Science
• Rocznik: 2001
• Tom: Vol. 9, nr 2
• Strony: 7-17
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Borowiecki, P.

• University of Zielona Góra Institute of Mathematics ,

autor

Kubale, M.

• Technical University of Gdańsk Foundations of Informatics Dept.,

Bibliografia

• [1] Borowiecki P., (2000) Efektywność algorytmów kolorowania grafów w trybie online, Zeszyty Naukowe Politechniki Śląskiej, ser. Automatyka 131 11-23 (in Polish).
• [2] Borowiecki P., (2000a) Algorytmy kolorowania grafów w trybie on-line, Ph.D. Thesis (in Polish), Faculty of Electronics, Telecommunications and Informatics, Technical University of Gdańsk.
• [3] Brélaz D., (1979) New methods to color the vertices of a graph, Communications of ACM 22 251-256.
• [4] Gyárfás A., Lehel J., (1988) On-line and First-Fit colorings of graphs, Journal of Graph Theory 12 (2) 217-227.
• [5] Gyárfás A., Lehel J., (1990) First-Fit and on-line chromatic number of families of graphs, Ars Combinatoria 29C 168-176.
• [6] Gyárfás A., Lehel J., (1991) Effective on-line coloring of P5-free graphs, Combinatorica 11 (2) 181-184.
• [7] Hansen P., Kuplinsky., (1990) Slightly hard-to-color graphs, Congressus Numerantium 78 81-98.
• [8] Hansen P., Kuplinsky., (1991) The smallest hard-to-color graph, Discrete Mathematics 96 199-212.
• [9] Janczewski R., Kubale M., Manuszewski K., Piwakowski K., (2001) The smallest hard-to-color graph for algorithm DSATUR, Discrete Mathematics 236 151-165.
• [10] Johnson D.S., (1974) Worst case behavior of graph coloring algorithms, Proc. 5-th S-E Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica., Winnipeg, 513-527.
• [11] Kierstead H.A., Qin J., (1995) Coloring interval graphs with first-Rt, Discrete Mathematics 144 47-57.
• [12] Kierstead H.A., Penrice S.G. and Trotter W.T., (1995) On-line and First-Fit coloring of graphs that do not induce P5, SIAM J. Disc. Math. 8 485-498.
• [13] Kubale M., Pakulski J., Piwakowski K., (1997) The smallest hard-to-color graph for the SL algorithm, Discrete Mathematics 164 197-212.
• [14] Kubale M., Manuszewski K., GIARO K., (2001) On the smallest hard to color sequentially graph, Congressus Numerantium (in press).
• [15] Lovasz L., Saks M. and Trotter W.T., (1989) An on-line graph coloring algorithm with sublinear performance ratio, Discrete Mathematics 75 319-325.
• [16] Manuszewski K., (1997) Grafy algorytmicznie trudne do kolorowania, Ph.D. Thesis (in Polish), Faculty of Electronics, Telecommunications and Informatics, Technical University of Gdańsk.
• [17] Matula D.W., Marble G. and Isaacson D., (1972) Graph coloring algorithms, in: Graph Theory and Computing, New York, Academic Press, 109-122.
• [18] Ślusarek M., (1989) A coloring algorithm for interval graphs, Mathematical Foundations of Computer Science '89, LNCS 379, Springer, 471-480.
• [19] Ślusarek M., (1995) Optimal on-line coloring of circular arc graphs, RAIRO Journal on Information Theory and Applications 29 423-429.
• [20] Ślusarek M., (1993) A lower bound for the First-Fit coloring of interval graphs, Zeszyty Naukowe Uniwersytetu Jagiellońskiego, Prace Informatyczne 29 423-429.
• [21] Welsh D.J., Powell M.B., (1967) An upper bound for the chromatic number of a graph and its application to timetabling problem, Computer Journal 10 85-86.