Balanced Total Coloring of the Double-Star Snark
Abstract
In 2016, Dantas et al. proposed the question about the existence of a Type 1 cubic graph with girth at least 5 and equitable total chromatic number 5, which motivated our result. We prove that Double Star snark have equitable total chromatic number 4, contributing as a negative evidence to this question.References
Araújo, R. and Sasaki, D. (2023). Coloraçao total equilibrada dos snarks de loupekine. In Anais do VIII Encontro de Teoria da Computação, pages 20–24. SBC.
Behzad, M. (1965). Graphs and Their Chromatic Numbers. PhD thesis, Michigan State University, Michigan.
Campos, C., Dantas, S., and de Mello, C. (2011). The total-chromatic number of some families of snarks. Discrete Math., 311:984–988.
Cavicchioli, A., Murgolo, T., Ruini, B., and Spaggiari, F. (2003). Special classes of snarks. Acta Applicandae Mathematica, 76:57–88.
Cordeiro, L., Dantas, S., and Sasaki, D. (2017). On equitable total colouring of loupekine snarks and their products. Mat. Cont., 45:77–85.
Dantas, S., de Figueiredo, C. M. H., Mazzuoccolo, G., Preissman, M., dos Santos, V. F., and Sasaki, D. (2016). On the equitable total chromatic number of cubic graphs. Discrete Appl. Math., 209:84–91.
Fu, H.-L. (1994). Some results on equalized total coloring. Congressus numerantium, pages 111–120.
Isaacs, R. (1975). Loupekhine’s snarks: A bi-family of non-tait-colorable graphs. Tec. Report.
Rosenfeld, M. (1971). On the total chromatic number of a graph. Israel J. Math, pages 396–402.
Sasaki, D., Dantas, S., de Figueiredo, C. M. H., Mazzuoccolo, G., and Preissman, M. (2014). The hunting of a snark with total chromatic number 5. Discrete Appl. Math., 164:470–481.
Tait, P. G. (1878-1880). Remarks on the colouring of maps. In Proceedings of the RSE, pages 501–503, 729, Edinburgh, Scotland.
Vizing, V. (1964). On an estimate of the chromatic class of a p-graph. Diskret. Analiz., pages 25–30.
Wang, W. (2002). Equitable total coloring of graphs with maximum degree 3. Graphs Comb, 18:677–685.
Behzad, M. (1965). Graphs and Their Chromatic Numbers. PhD thesis, Michigan State University, Michigan.
Campos, C., Dantas, S., and de Mello, C. (2011). The total-chromatic number of some families of snarks. Discrete Math., 311:984–988.
Cavicchioli, A., Murgolo, T., Ruini, B., and Spaggiari, F. (2003). Special classes of snarks. Acta Applicandae Mathematica, 76:57–88.
Cordeiro, L., Dantas, S., and Sasaki, D. (2017). On equitable total colouring of loupekine snarks and their products. Mat. Cont., 45:77–85.
Dantas, S., de Figueiredo, C. M. H., Mazzuoccolo, G., Preissman, M., dos Santos, V. F., and Sasaki, D. (2016). On the equitable total chromatic number of cubic graphs. Discrete Appl. Math., 209:84–91.
Fu, H.-L. (1994). Some results on equalized total coloring. Congressus numerantium, pages 111–120.
Isaacs, R. (1975). Loupekhine’s snarks: A bi-family of non-tait-colorable graphs. Tec. Report.
Rosenfeld, M. (1971). On the total chromatic number of a graph. Israel J. Math, pages 396–402.
Sasaki, D., Dantas, S., de Figueiredo, C. M. H., Mazzuoccolo, G., and Preissman, M. (2014). The hunting of a snark with total chromatic number 5. Discrete Appl. Math., 164:470–481.
Tait, P. G. (1878-1880). Remarks on the colouring of maps. In Proceedings of the RSE, pages 501–503, 729, Edinburgh, Scotland.
Vizing, V. (1964). On an estimate of the chromatic class of a p-graph. Diskret. Analiz., pages 25–30.
Wang, W. (2002). Equitable total coloring of graphs with maximum degree 3. Graphs Comb, 18:677–685.
Published
2024-07-21
How to Cite
ARAÚJO, Rieli; SASAKI, Diana.
Balanced Total Coloring of the Double-Star Snark. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 9. , 2024, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 21-24.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2024.2115.
