Combinatorial coloring of 3-colorable graphs

arXiv1205.1254MaRDI QIDQ6232820FDOQ6232820

Authors: Ken-ichi Kawarabayashi, Mikkel Thorup 

Publication date: 6 May 2012

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 $O(n^{4/11})$ colors. This is the first combinatorial improvement of Blum's $O(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.

This page was built for publication: Combinatorial coloring of 3-colorable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6232820)