Coloring \(k\)-colorable graphs using smaller palettes
type: Item
instance of: scholarly article
zbMATH Open document ID: 0995.05061
author: Eran Halperin
author: Ram Nathaniel
author: Uri Zwick
publication date: 2002-10-24T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1699241
zbMATH Keywords: coloring algorithm
zbMATH Keywords: \(k\)-colorable graphs
MaRDI profile type: MaRDI publication profile
Recommended article: Coloring -colorable graphs using relatively small palettes
Recommended article: Q5369515
Recommended article: Coloring Graphs with Constraints on Connectivity
Recommended article: On coloring graphs with locally small chromatic number
Recommended article: Coloring subgraphs with restricted amounts of hues
Recommended article: Intervalizing k-colored graphs
Recommended article: Colorful subgraphs in Kneser-like graphs
Recommended article: Coloring Graphs with Minimal Edge Load
Recommended article: A polyhedral approach for graph coloring
Recommended article: Q4947488
title: Coloring \(k\)-colorable graphs using smaller palettes
review text: 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].
reviewed by: Gerd Wegner
description: scientific article; zbMATH DE number 1699241