All Direct Product C5 × Kn Graphs Are Type 1
DOI:
https://doi.org/10.5540/03.2026.012.01.0243Palavras-chave:
Graph Theory, Total Coloring, Direct ProductResumo
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.
Downloads
Referências
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.
