Coloring \(k\)-colorable graphs using smaller palettes
Refining a coloring algorithm given by \textit{D. Karger}, \textit{R. Motwani} and \textit{M. Sudan} [J. AMC 45, No. 2, 246-265 (1998; Zbl 0904.68116)] and thus improving their result the present authors are able to color 3-colorable graphs on \(n\) vertices with maximum degree \(\Delta\) in polynomial time with \(O((\Delta\log\Delta)^{1/3}\log n)\) colors. Combining the paper cited above with techniques of other authors they obtain an algorithm which colors 4-colorable graphs on \(n\) vertices in polynomial time using \(\widetilde O(n^{7/19})\) colors. Both results hold for \(k\)-colorable graphs with modified bounds.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].
scientific article; zbMATH DE number 1699241