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 $\text{ds}>\sqrt{n}$, we can, in polynomial time, make progress towards a $k$-coloring for some $k=\sqrt{n\mathrm{/}\text{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 $\text{tO}(n^{0.19747})$ colors suffice for coloring 3-colorable graphs. This improves on the previous best bound of $\text{tO}(n^{0.19996})$ by Kawarabayashi and Thorup in 2017.