An on-line graph coloring algorithm with sublinear performance ratio

Bean, 1976, Effective coloration, J. Symbolic Logic, 41, 469, 10.2307/2272247 J.L. Bentley and C.C. McGeoch, Worst-case analyses of self-organizing sequential search heuristics, Communications of ACM, to appear. Bitner, 1979, Heuristics that dynamically organize data structures, SIAM J. Comp., 8, 82, 10.1137/0208007 Borodin, 1987, An online algorithm for metrical task systems, Proc. 19th Annual ACM Symp. on Theory of Computing, 373 Chung, 1987, Dynamic search in graphs F.R.K. Chung, R.L. Graham and M. Saks, A dynamic location problem for graphs, Preprint. (a) Gyárfás and J. Lehel, On-line and first-fit colorings of graphs, J. Graph Theory, to appear. Gonnet, 1979, Toward self-organizing search heuristics, Proc. 20th IEEE Symp. Foundations of Comp. Sci., 169 Johnson, 1974, Worst case performance bounds for simple one-dimensional bin packing algorithms, SIAM J. Computing, 3, 299, 10.1137/0203025 Karlin, 1986, Competitive snoopy catching, Proc. 27th IEEE Symp. Foundations of Comp. Sci., 244 Kierstead, 1981, An effective version of Dilworth's theorem, Trans. Amer. Math. Soc., 268, 63 H.A. Kierstead, The linearity of first-fit colorings of interval graphs, SIAM J. on Discrete Math., to appear. H.A. Kierstead, G.F. McNulty and W.T. Trotter, A theory of recursive dimension for ordered sets, Order 1, 67-82. Kierstead, 1981, An extremal problem in recursive combinatorics, Congressus Numerantium, 33, 143 Manasse, 1988, Competitive algorithms for on-line problems, Proc. 20th Annual Symp. on Theory of Computing Rivest, 1976, On self-organizing sequential search heuristics, CACM, 19, 63, 10.1145/359997.360000 Schmerl, 1984, Recursion theoretic aspects of graphs and order, 467 Sleator, 1985, Amortized efficiency of list update and paging rules, CACM, 23, 202, 10.1145/2786.2793 M. Szegedy, personal communication. Tarjan, 1985, Amortized computational complexity, SIAM J. Alg. Disc. Methods, 6, 306, 10.1137/0606031 Wigderson, 1983, Improving the performance guarantee for approximate graph coloring, J. ACM, 30, 729, 10.1145/2157.2158 Woodall, 1974, Problem no. 4, 13, 202