On-line coloringk-colorable graphs |
| |
Authors: | H A Kierstead |
| |
Institution: | (1) Department of Mathematics, Arizona State University, 85287 Tempe, AZ, USA |
| |
Abstract: | We show that for anyk, there exists an on-line algorithm that will color anyk-colorable graph onn vertices withO(n
1−1/k!
) colors. This improves the previous best upper bound ofO(nlog(2k−3)
n/log(2k−4)
n) due to Lovász, Saks, and Trotter. In the special casesk=3 andk=4 we obtain on-line algorithms that useO(n
2/3log1/3
n) andO(n
5/6log1/6
n) colors, respectively. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|