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.