Three Questions about Equitable Total Coloring of Small Cubic Graphs
Resumo
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.
Referências
Behzad, M. (1965). Graphs and their chromatic numbers. PhD thesis, Michigan State University.
Chetwynd and Hilton, A. (1988). Some refinements of the total chromatic number conjecture. Congressus Numerantium, 66:195–216.
Dantas, S., Figueiredo, C., Preissmann, M., Sasaki, D., and dos Santos, V. (2016). On the equitable total chromatic number of cubic graphs. Discrete Applied Mathematics, 209:84–91.
Stemock, B. (2020). On the equitable total (k + 1)-coloring of k-regular graphs. RoseHulman Undergraduate Mathematics Journal, 21:Article 7.
Vizing, V. (1964). On an estimate of the chromatic class of a p-graph. Discret Analiz, 3:25–30.
