Coloring \(k\)-colorable graphs using smaller palettes (Q2768312)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Coloring \(k\)-colorable graphs using smaller palettes |
scientific article; zbMATH DE number 1699241
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Coloring \(k\)-colorable graphs using smaller palettes |
scientific article; zbMATH DE number 1699241 |
Statements
24 October 2002
0 references
coloring algorithm
0 references
\(k\)-colorable graphs
0 references
0.98973995
0 references
0.8875197
0 references
0.88677174
0 references
0.88541317
0 references
0 references
0.8850378
0 references
0.88484585
0 references
0.8838131
0 references
Coloring \(k\)-colorable graphs using smaller palettes (English)
0 references
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].
0 references
