TOTAL COLORING WITH DELTA-PLUS-POLY(LOG-DELTA) COLORS

Authors
HIND H MOLLOY M REED B
Citation
H. Hind et al., TOTAL COLORING WITH DELTA-PLUS-POLY(LOG-DELTA) COLORS, SIAM journal on computing (Print), 28(3), 1999, pp. 816-821
Citations number
15
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing (Print) → ACNP
ISSN journal
00975397
Volume
28
Issue
3
Year of publication
1999
Pages
816 - 821
Database
ISI
SICI code
0097-5397(1999)28:3<816:TCWDC>2.0.ZU;2-K
Abstract
We provide a polynomial time algorithm which finds a total coloring of any graph with maximum degree Delta, Delta sufficiently large, using at most Delta + 8 log(8) Delta colors. This improves the best previous upper bound on the total chromatic number of Delta + 18 Delta(1/3) lo g(3 Delta).