DMS Combinatorics Seminar

Speaker: Songling Shan (Auburn University)

Title: Total coloring graphs with large maximum degree

Abstract: We prove that for any graph $G$, the total chromatic number of $G$ is at most $\Delta(G)+2\lceil \frac{|V(G)|}{\Delta(G)+1} \rceil$.

This saves one color in comparison with a result of Hind from 1992 In particular, our result says that if $\Delta(G)\ge \frac{1}{2}|V(G)|$, then $G$ has a total colouring using at most $\Delta(G)+4$ colors.  When $G$ is regular and has a sufficient number of vertices, we can actually save an additional two colors. Specifically, we prove that for any  $0<\varepsilon <1$, there exists $n_0\in \mathbb{N}$ such that: if $G$ is an $r$-regular graph on $n \ge n_0$ vertices with $r\ge \frac{1}{2}(1+\varepsilon) n$, then $\chi_T(G) \le \Delta(G)+2$. This confirms the Total Coloring Conjecture for such graphs $G$.

This is joint work with Aseem Dalal and Jessica McDonald.