KAIST Discrete Math Seminar

A total coloring is a combination of a vertex coloring and an edge coloring of a graph: every vertex and every edge is assigned a color and any two adjacent/incident objects must receive distinct colors. One of the main open problems in the area of graph colorings is the Total Coloring Conjecture of Behzad and Vizing from the 1960’s asserting that every graph has a total coloring with at most D+2 colors where D is its maximum degree.

Fractional colorings are linear relaxation of ordinary colorings. In the setting of fractional total colorings, the Total Coloring Conjecture was proven by Kilakos and Reed. In the talk, we will present a proof of the following recent conjecture of Reed:

For every real ε>0 and integer D, there exists g such that every graph with maximum degree D and girth at least g has total fractional chromatic number at most D+1+ε.

For D=3 and D=4,6,8,10,…, we prove the conjecture in a stronger
form: there exists g such that every graph with maximum degree D and girth at least g has total fractional chromatic number equal to D+1.

Joint work with Tomás Kaiser, František Kardoš, Andrew King and Jean-Sébastien Sereni.