Combinatorial coloring of 3-colorable graphs

2012/05/06 by Ken‐ichi Kawarabayashi, Mikkel Thorup, Kawarabayashi, Ken-ichi +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1205.1254

openalex publication_date 2012/05/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. We present a combinatorial algorithm getting down to \tO(n^4/11) colors. This is the first combinatorial improvement of Blum's \tO(n^3/8) bound from FOCS'90. Like Blum's algorithm, our new algorithm composes nicely with recent semi-definite approaches. The current best bound is O(n^0.2072) colors by Chlamtac from FOCS'07. We now bring it down to O(n^0.2038) colors.

Cited by

• Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of\n Satisfiable CSPs

Related

• Better coloring of 3-colorable graphs
• Coloring k-colorable graphs using relatively small palettes
• Exponential Time Approximation for Coloring 3-Colorable Graphs
• 3-Coloring in Time O(1.3217ⁿ)
• P=NP