摘要: Lovasz, Saks, and Trotter showed that there exists an on-line algorithm which will color any on-linek-colorable graph onn vertices withO(nlog(2k−3) n/log(2k−4) n) colors. Vishwanathan at least Ω(log k−1 n/k k ) colors are needed. While these remain the best known bounds, they give a distressingly weak approximation of number required. In this article we study case perfect graphs. We prove withn 10k/loglogn Vishwanathan's techniques can be slightly modified to show his lower bound also holds for This suggests is far from tight in general case.
springer.com
elsevier.com
sci-hub.se 参考文章(6)
H. A. Kierstead, The linearity of first-fit coloring of interval graphs SIAM Journal on Discrete Mathematics. ,vol. 1, pp. 526- 530 ,(1988) , 10.1137/0401048
Henry A. Kierstead, Stephen G. Penrice, William T. Trotter, On-Line and First-Fit Coloring of Graphs That Do Not Induce $P_5$ SIAM Journal on Discrete Mathematics. ,vol. 8, pp. 485- 498 ,(1995) , 10.1137/S0895480191218861
Sundar Vishwanathan, Randomized online graph coloring Journal of Algorithms. ,vol. 13, pp. 657- 669 ,(1992) , 10.1016/0196-6774(92)90061-G
H. A. Kierstead, S. G. Penrice, W. T. Trotter, On-Line Coloring and Recursive Graph Theory SIAM Journal on Discrete Mathematics. ,vol. 7, pp. 72- 89 ,(1994) , 10.1137/S0895480192224737
S. Irani, Coloring inductive graphs on-line foundations of computer science. pp. 470- 479 ,(1990) , 10.1109/FSCS.1990.89568
András Gyárfás, Jenö Lehel, On‐line and first fit colorings of graphs Journal of Graph Theory. ,vol. 12, pp. 217- 227 ,(1988) , 10.1002/JGT.3190120212