Fractional total colourings of graphs of high girth

Fractional total colourings of graphs of high girth

-
Andrew King, Columbia University
Fine Hall 224

The total graph $T(G)$ has vertex set $V(G) \cup 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.