Better coloring of 3-colorable graphs
<|reference_start|>Better coloring of 3-colorable graphs: We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. This is one of the most challenging problems in graph algorithms.   In this paper using Blum's notion of ``progress'', we develop a new combinatorial algorithm for the following: Given any 3-colorable graph with minimum degree $\ds>\sqrt n$, we can, in polynomial time, make progress towards a $k$-coloring for some $k=\sqrt{n/\ds}\cdot n^{o(1)}$.   We balance our main result with the best-known semi-definite(SDP) approach which we use for degrees below $n^{0.605073}$. As a result, we show that $\tO(n^{0.19747})$ colors suffice for coloring 3-colorable graphs. This improves on the previous best bound of $\tO(n^{0.19996})$ by Kawarabayashi and Thorup in 2017.<|reference_end|>
@article{kawarabayashi2024better,
    title={Better coloring of 3-colorable graphs},
    author={Ken-ichi Kawarabayashi and Mikkel Thorup and Hirotaka Yoneda},
    journal={arXiv preprint arXiv:2406.00357},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.00357},
    primaryClass={cs.DS math.CO}
}