Combinatorial coloring of 3-colorable graphs

Ken-ichi Kawarabayashi; Mikkel Thorup

doi:10.1109/FOCS.2012.16

Combinatorial coloring of 3-colorable graphs

Ken-ichi Kawarabayashi, Mikkel Thorup

Department of Computer Science

14 Citations (Scopus)

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 Õ(n^4/11) colors. This is the first combinatorial improvement of Blum's Õ(n^3/8) bound from FOCS'90. Like Blum's algorithm, our new algorithm composes nicely with recent semi-definite programming 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.2049) colors.

Original language	English
Title of host publication	2012 IEEE 53rd Annual Symposium on Foundations of Computer Science
Number of pages	8
Publisher	IEEE
Publication date	2012
Pages	68-75
ISBN (Print)	978-1-4673-4383-1
DOIs	https://doi.org/10.1109/FOCS.2012.16
Publication status	Published - 2012
Event	IEEE 53rd Annual Symposium on Foundations of Computer Science - New Brunswick, New Jersey, United States Duration: 20 Oct 2012 → 23 Oct 2012 Conference number: 53

Conference

Conference	IEEE 53rd Annual Symposium on Foundations of Computer Science
Number	53
Country/Territory	United States
City	New Brunswick, New Jersey
Period	20/10/2012 → 23/10/2012

Access to Document

10.1109/FOCS.2012.16

Cite this

@inproceedings{4ca73b18f9bc4284a9dd6ef10170b5fa,

title = "Combinatorial coloring of 3-colorable graphs",

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}(n4/11) colors. This is the first combinatorial improvement of Blum's {\~O}(n3/8) bound from FOCS'90. Like Blum's algorithm, our new algorithm composes nicely with recent semi-definite programming approaches. The current best bound is O(n0.2072) colors by Chlamtac from FOCS'07. We now bring it down to O(n0.2049) colors.",

keywords = "computational complexity, graph colouring, mathematical programming, 3-colorable graph, {\~O}(n0.2072) colors, {\~O}(n0. 2049) colors, {\~O}(n4/11) colors, combinatorial coloring algorithm, polynomial time, semi-definite programming approaches, Algorithm design and analysis, Approximation algorithms, Approximation methods, Color, Computer science, Electronic mail, Polynomials, Approximation Algorithms, Graph Coloring",

author = "Ken-ichi Kawarabayashi and Mikkel Thorup",

year = "2012",

doi = "10.1109/FOCS.2012.16",

language = "English",

isbn = "978-1-4673-4383-1",

pages = "68--75",

booktitle = "2012 IEEE 53rd Annual Symposium on Foundations of Computer Science",

publisher = "IEEE",

note = "IEEE 53rd Annual Symposium on Foundations of Computer Science ; Conference date: 20-10-2012 Through 23-10-2012",

}

TY - GEN

T1 - Combinatorial coloring of 3-colorable graphs

AU - Kawarabayashi, Ken-ichi

AU - Thorup, Mikkel

N1 - Conference code: 53

PY - 2012

Y1 - 2012

N2 - 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 Õ(n4/11) colors. This is the first combinatorial improvement of Blum's Õ(n3/8) bound from FOCS'90. Like Blum's algorithm, our new algorithm composes nicely with recent semi-definite programming approaches. The current best bound is O(n0.2072) colors by Chlamtac from FOCS'07. We now bring it down to O(n0.2049) colors.

AB - 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 Õ(n4/11) colors. This is the first combinatorial improvement of Blum's Õ(n3/8) bound from FOCS'90. Like Blum's algorithm, our new algorithm composes nicely with recent semi-definite programming approaches. The current best bound is O(n0.2072) colors by Chlamtac from FOCS'07. We now bring it down to O(n0.2049) colors.

KW - computational complexity

KW - graph colouring

KW - mathematical programming

KW - 3-colorable graph

KW - Õ(n0.2072) colors

KW - Õ(n0. 2049) colors

KW - Õ(n4/11) colors

KW - combinatorial coloring algorithm

KW - polynomial time

KW - semi-definite programming approaches

KW - Algorithm design and analysis

KW - Approximation algorithms

KW - Approximation methods

KW - Color

KW - Computer science

KW - Electronic mail

KW - Polynomials

KW - Approximation Algorithms

KW - Graph Coloring

U2 - 10.1109/FOCS.2012.16

DO - 10.1109/FOCS.2012.16

M3 - Article in proceedings

SN - 978-1-4673-4383-1

SP - 68

EP - 75

BT - 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science

PB - IEEE

T2 - IEEE 53rd Annual Symposium on Foundations of Computer Science

Y2 - 20 October 2012 through 23 October 2012

ER -

Combinatorial coloring of 3-colorable graphs

Abstract

Conference

Access to Document

Fingerprint

Cite this