On-line coloring k-colorable graphs

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


We show that for any k, there exists an on-line algorithm that will color any k-colorable graph on n vertices with O(n1-1/k!) colors. This improves the previous best upper bound of O(n log (2k-3) n/log(2k-4) n) due to Lovász, Saks, and Trotter. In the special cases k = 3 and k = 4 we obtain on-line algorithms that use O(n2/3 log1/3 n) and O(n5/6 log1/6 n) colors, respectively.

Original languageEnglish (US)
Pages (from-to)93-104
Number of pages12
JournalIsrael Journal of Mathematics
StatePublished - Jan 1 1998

ASJC Scopus subject areas

  • Mathematics(all)


Dive into the research topics of 'On-line coloring k-colorable graphs'. Together they form a unique fingerprint.

Cite this