2
[1205.1254] Combinatorial coloring of 3-colorable graphs
source link: https://arxiv.org/abs/1205.1254
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Discrete Mathematics
[Submitted on 6 May 2012]
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(n0.2072) colors by Chlamtac from FOCS'07. We now bring it down to O(n0.2038) colors.
| Subjects: | Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO) |
| Cite as: | arXiv:1205.1254 [cs.DM] |
| (or arXiv:1205.1254v1 [cs.DM] for this version) | |
| https://doi.org/10.48550/arXiv.1205.1254 |
Submission history
From: Ken-ichi Kawarabayashi [view email][v1] Sun, 6 May 2012 23:25:11 UTC (14 KB)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK