Fractional total colourings of graphs of high girth
The total graph T(G) has vertex set V(G) union E(G), in which
two vertices of T(G) are adjacent precisely if they arise from (i) two
adjacent vertices of G, (ii) two incident edges of G, or (iii) an edge
of G and one of its endpoints. The (fractional) total chromatic number of
G is the (fractional) chromatic number of T(G).
It is known that the fractional total chromatic number is between
Delta+1 and Delta+2, where Delta is the maximum degree. Reed recently
announced a conjecture that the fractional total chromatic number
approaches Delta+1 as the girth of a graph increases (for fixed Delta);
this would be yet another similarity between total colourings and edge
colourings. We prove this conjecture using the approach of l-path
decompositions and a randomized method for choosing total stable sets of G.
This is joint work with Tomas Kaiser and Dan Kral.