@techreport{TD:100861,
	att_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.
}},
	att_authors={mt2514},
	att_categories={},
	att_copyright={{IEEE}},
	att_copyright_notice={{This version of the work is reprinted here with permission of IEEE for your personal use. Not for redistribution. The definitive version was published in 2012. {{, 2012-10-20}}
}},
	att_donotupload={},
	att_private={false},
	att_projects={},
	att_tags={},
	att_techdoc={true},
	att_techdoc_key={TD:100861},
	att_url={http://web1.research.att.com:81/techdocs_downloads/TD:100861_DS1_2012-04-25T21:50:29.204Z.pdf},
	author={Mikkel Thorup and Ken-ichi Kawarabayashi,  National Institute of Informatics, Tokyo},
	institution={{Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012)}},
	month={October},
	title={{Combinatorial coloring of 3-colorable graphs}},
	year=2012,
}