Lower bounds for on-line graph coloring

ABSTRACT

An algorithm for vertex-coloring graphs is said to be online if each vertex is irrevocably assigned a color before any later vertices are considered. We show that such algorithms are inherently ineffective. The performance ratio of any such algorithm can be no better than &OHgr;(n/log2 n), even for randomized algorithms against oblivious adversary. We also show that various means of relaxing the constraints of the on-line model do not reduce these lower bounds. The features include presenting the input in blocks of log2 n vertices, recoloring any fraction of the vertices, presorting vertices according to degree, and disclosing the adversary's previous coloring.

REFERENCES

• 1: D. Bean. Effective coloration. J. Symbolic Logic, 41:469-480, 1976.
• 2: F. R. K. Chung, R. L. Graham, and M. E. Saks. A dynamic location problem for graphs. Combinatorica, 9(2):111-131, 1080.
• 3: G. Gambosi, A. Postiglione, and M. Talamo. New algorithms for on-line bin packing, in First Italian Con}erence on Algorithms, pages 44-59, 1990.
• 4: A. Gy~rf~s and J. Lehel. On-line and first fit colorings of graphs. J. Graph Theory, 12(2):217-227, 1988.
• 5: M. M. Halld6rsson. Improved performance guarantee for randomized on-line graph coloring. Technical Report 91-35, DIMACS, May 1991.
• 6: Magnfis M. Halld6rsson and M~ri6 Szegedy. Lower bounds for on-line graph coloring. In D. D. Sleator, editor, Proc. of DIMACS Workshop on On-Line Algorithms, Feb. 1991.
• 7: S. Irani. On-line coloring inductive graphs. In Proc. 31st Ann. IEEE Syrup. on Found. of Comp. Sci., pages 470-479, Oct. 1990. (Improved lookahead results in a later manuscript.)
• 8: D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput., 3(4):299-325, Dec. 1974.
• 9: Ming-Yang Kao , Stephen R. Tate, Online matching with blocked input, Information Processing Letters, v.38 n.3, p.113-116, May 7, 1991 [doi>10.1016/0020-0190(91)90231-6]
• 10: H. A. Kierstead and W. T. Trotter. An extremal problem in recursive combinatorics. In Proc. 12th Southeastern Con/. on Combinatorics, Graph Theory, and Computing. Congressus Numerantiurn XXXIII, pages 143-153, 1981.
• 11: L. Lovsz , M. Saks , W. T. Trotter, An on-line graph coloring algorithm with sublinear performance ratio, Discrete Mathematics, v.75 n.1-3, p.319-325, 1989 [doi>10.1016/0012-365X(89)90096-4]
• 12: David W. Matula , Leland L. Beck, Smallest-last ordering and clustering and graph coloring algorithms, Journal of the ACM (JACM), v.30 n.3, p.417-427, July 1983 [doi>10.1145/2402.322385]
• 13: S. Vishwanathast. Randomized online graph coloring. In Proc. 31st Ann. iEEE Syrup. on Found. o/Comp. Sci., pages 464-469, Oct. 1990.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory, Verification