Infinite families of Kochol superpositions of Goldberg with Blowup snarks are Type 1

• Giovanna A. B. Penao UFF
• Miguel A. D. R. Palma UFF
• Simone Dantas UFF
• Diana Sasaki UERJ

DOI: https://doi.org/10.5753/etc.2024.2072

Resumo

Uma q-coloração total de G é uma atribuição de q cores aos vértices e arestas de um grafo G, de forma que elementos adjacentes ou incidentes tenham cores diferentes. A Conjectura da Coloração Total (TCC) afirma que uma coloração total ótima de G é pelo menos ∆ + 1 e no máximo ∆ + 2 cores. Determinamos que todos os membros de novas famílias infinitas de snarks obtidos pela superposição Kochol de snarks de Goldberg com snarks Blowup são Tipo 1.

Referências

Behzad, M. (1965). Graphs and their chromatic numbers. Michigan State University.

Brinkmann, G., Preissmann, M. and Sasaki, D.(2015). Snarks with total chromatic number 5, In Discrete Mathematics and Theoretical Computer Science, 17(1), pages 369–382.

Campos, C. N., Dantas, S., and de Mello, C. P. (2011). The total-chromatic number of some families of snarks. In Discrete Mathematics, 311(12), pages 984-988.

Cavicchioli, A., Murgolo, T. E., Ruini, B., and Spaggiari, F. (2003). Special classes of snarks. In Acta Applicandae Mathematica, 76, pages 57-88.

Goldberg, M. K. (1981). Construction of class 2 graphs with maximum vertex degree 3. In Journal of Combinatorial Theory, Series B, 31(3), pages 282-291.

Hägglund, J. (2016). On snarks that are far from being 3-edge colorable. In The Electronic Journal of Combinatorics, 23(2), pages 2-6.

Isaacs, R. (1975). Infinite families of nontrivial trivalent graphs which are not Tait colorable. In The American Mathematical Monthly, 82(3), pages 221-239.

Kochol, M. (1996). Snarks without small cycles. In journal of combinatorial theory, Series B, 67(1), pages 34-47.

Palma, M. A., Dantas, S., and Sasaki, D. (2023). Kochol superposition of Goldberg with Semi-blowup snarks is Type 1. Procedia Computer Science, 223, pages 250-257.

Palma, M. A., Gonçalves, I. F., Sasaki, D., and Dantas, S. (2023). On total coloring and equitable total coloring of infinite snark families. In RAIRO-Operations Research, 57(5), pages 2619-2637.

Rosenfeld, M. (1971). On the total coloring of certain graphs. In Israel Journal of Mathematics, 9, pages 396-402.

Vijayaditya, N. (1971). On total chromatic number of a graph. In Journal of the London Mathematical Society, 2(3), pages 405-408.

Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph. In Diskret analiz, 3, pages 25-30.