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 > n, we can, in polynomial time, make progress towards a k-coloring for some k=n/ 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 (n^0. 19747) colors suffice for coloring 3-colorable graphs. This improves on the previous best bound of (n^0. 19996) by Kawarabayashi and Thorup in 2017.