Infinite families of Kochol superpositions of Goldberg with Blowup snarks are Type 2
Abstract
A q-total coloring of a graph G is an assignment of q colors to the vertices and edges of G, so that adjacent or incident elements have different colors. The Total Coloring Conjecture (TCC) asserts that an optimum total coloring of G has at least ∆+1 and at most ∆+2 colors. We determine that all members of new infinite families of snarks obtained by the Kochol superposition of Goldberg with Blowup snarks are Type 1.References
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.
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.
Published
2024-07-21
How to Cite
PENAO, Giovanna A. B.; PALMA, Miguel A. D. R.; DANTAS, Simone; SASAKI, Diana.
Infinite families of Kochol superpositions of Goldberg with Blowup snarks are Type 2. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 9. , 2024, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 11-15.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2024.2072.
