Combinatorial Coloring of 3-Colorable Graphs
Combinatorial Coloring of 3-Colorable Graphs
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.
- University of Copenhagen Denmark
- University of Copenhagen Denmark
FOS: Computer and information sciences, 3-colorable graph, polynomial time, Discrete Mathematics (cs.DM), Color, Approximation methods, Polynomials, Õ(n4/11) colors, semi-definite programming approaches, Computer Science - Data Structures and Algorithms, Õ(n0.2072) colors, Algorithm design and analysis, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), graph colouring, computational complexity, combinatorial coloring algorithm, Computer science, Approximation algorithms, Electronic mail, Graph Coloring, Combinatorics (math.CO), mathematical programming, Õ(n0. 2049) colors, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, 3-colorable graph, polynomial time, Discrete Mathematics (cs.DM), Color, Approximation methods, Polynomials, Õ(n4/11) colors, semi-definite programming approaches, Computer Science - Data Structures and Algorithms, Õ(n0.2072) colors, Algorithm design and analysis, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), graph colouring, computational complexity, combinatorial coloring algorithm, Computer science, Approximation algorithms, Electronic mail, Graph Coloring, Combinatorics (math.CO), mathematical programming, Õ(n0. 2049) colors, Computer Science - Discrete Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).7 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!