All Direct Product C5 × Kn Graphs Are Type 1

Autores/as

  • Diane Castonguay Universidade Federal de Goiás
  • Celina M. H. de Figueiredo Universidade Federal do Rio de Janeiro
  • Luis A. B. Kowada Universidade Federal do Rio de Janeiro
  • Caroline S. R. Patrão Instituto Federal de Educação, Ciência e Tecnologia de Goiás
  • Diana Sasaki Universidade do Estado do Rio de Janeiro

DOI:

https://doi.org/10.5540/03.2026.012.01.0243

Palabras clave:

Graph Theory, Total Coloring, Direct Product

Resumen

A k-total coloring of a graph G is an assignment of k colors to the elements (vertices and edges) of G so that adjacent or incident elements have different colors. The total chromatic number is the smallest integer k for which G has a k-total coloring. The well known Total Coloring Conjecture states that the total chromatic number of a graph is either Δ(G) + 1 (called Type 1) or Δ(G) + 2 (called Type 2), where Δ(G) is the maximum degree of G. In this paper, we establish that all the direct product C5 × Kn graphs are Type 1, when n is odd and not a multiple of 5, providing evidence for the conjecture that all Cm × Kn graphs are Type 1.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

B. Alspach, J.-C. Bermond, and D. Sotteau. Decomposition Into Cycles I: Hamilton decompositions. In Proceedings of the NATO Advanced Research Workshop on Cycles et al., 1990, pp. 9–18. doi: https://doi.org/10.1007/978-94-009-0517-7_2.

M. Behzad, G. Chartrand, and J. K. Cooper Jr. “The colour numbers of complete graphs”. In: J. London Math. Soc. 42 (1967), pp. 226–228.

D. Castonguay, C. M. H. de Figueiredo, L. A. B. Kowada, C. S. R. Patrão, and D. Sasaki. “On total coloring the direct product of cycles and bipartite direct product of graphs”. In: Discrete Math. 346 (2023), p. 113340. doi: https://doi.org/10.1016/j.disc.2023.113340.

D. Castonguay, C. M. H. de Figueiredo, L. A. B. Kowada, C. S. R. Patrão, D. Sasaki, and M. Valencia-Pabon. “On total chromatic number of the direct product of cycles and complete graphs”. In: RAIRO Oper. Res. 58 (2024), pp. 1609–1632. doi: https://doi.org/10.1051/ro/2024045.

P. K. Jha. “Hamiltonian decompositions of products of cycles”. In: Indian J. Pure Appl. Math. 23.10 (1992), pp. 723–729.

M. Rosenfeld. “On the total chromatic number of a graph”. In: Israel J. Math. 9 (1971), pp. 396–402.

V. G. Vizing. “On an estimate of the chromatic class of a p-graph”. In: Diskret. Analiz. 3 (1964), pp. 25–30.

Descargas

Publicado

2026-02-13

Número

Vol. 12 Núm. 1 (2026): CNMAC 2025

Sección

Trabalhos Completos