Events

DMS Combinatorics Seminar

Time: Oct 09, 2024 (02:00 PM)
Location: 328 Parker Hall

Details:

Songling

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 Δ(G)+2|V(G)|Δ(G)+1.

This saves one color in comparison with a result of Hind from 1992 In particular, our result says that if Δ(G)12|V(G)|, then G has a total colouring using at most Δ(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<ε<1, there exists n0N such that: if G is an r-regular graph on nn0 vertices with r12(1+ε)n, then χT(G)Δ(G)+2. This confirms the Total Coloring Conjecture for such graphs G.

This is joint work with Aseem Dalal and Jessica McDonald.