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

Datalogisk Institut

14 Citationer (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.

Originalsprog	Engelsk
Titel	2012 IEEE 53rd Annual Symposium on Foundations of Computer Science
Antal sider	8
Forlag	IEEE
Publikationsdato	2012
Sider	68-75
ISBN (Trykt)	978-1-4673-4383-1
DOI	https://doi.org/10.1109/FOCS.2012.16
Status	Udgivet - 2012
Begivenhed	IEEE 53rd Annual Symposium on Foundations of Computer Science - New Brunswick, New Jersey, USA Varighed: 20 okt. 2012 → 23 okt. 2012 Konferencens nummer: 53

Konference

Konference	IEEE 53rd Annual Symposium on Foundations of Computer Science
Nummer	53
Land/Område	USA
By	New Brunswick, New Jersey
Periode	20/10/2012 → 23/10/2012

Emneord

computational complexity
graph colouring
mathematical programming
3-colorable graph
Õ(n0.2072) colors
Õ(n0. 2049) colors
Õ(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

Adgang til dokumentet

10.1109/FOCS.2012.16

Citationsformater

@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

Konference

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater