Three Questions about Equitable Total Coloring of Small Cubic Graphs

  • Matheus N. Adauto UFRJ
  • Celina M. H. de Figueiredo UFRJ
  • Diana Sasaki UERJ

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.

Palavras-chave: Graph theory, Cubic graphs, Equitable total coloring

Referências

Adauto, M. (2022). Equitable total coloring of small cubic graphs. Master’s thesis, Universidade Federal do Rio de Janeiro/COPPE.

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.
Publicado
31/07/2022
ADAUTO, Matheus N.; FIGUEIREDO, Celina M. H. de; SASAKI, Diana. Three Questions about Equitable Total Coloring of Small Cubic Graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 21-24. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2022.222596.