Three Questions about Equitable Total Coloring of Small Cubic Graphs - Adauto, Matheus N.; Figueiredo, Celina M. H. de; Sasaki, Diana (Anais do Encontro de Teoria da Computação (ETC); 2022: Anais do VII Encontro de Teoria da Computação, 2022)
A total coloring assigns colors to the vertices and edges of a graph without conflicts and it is called equitable if the cardinalities of any two color classes differ by at most 1. In 2020, Stemock considered equitable total colorings of small cubic graphs and conjectured that every 4-total coloring of a cubic graph with less than 20 vertices is equitable. We present counterexamples to Stemock’s conjecture. We determine that every 4-total coloring must be equitable on all cubic graphs with 6, 8, 10, and 14 vertices. On the other hand, for cubic graphs with 12, 16, and 18 vertices, we characterize the color class configurations that might allow a non-equitable 4-total coloring. We prove that a cubic graph of 12 vertices is the smallest counterexample to Stemock’s conjecture.