On total coloring the direct product of cycles and bipartite direct product of graphs

• Published in: Discrete mathematics 2023-06, Vol.346 (6), p.113340, Article 113340
• Main Authors: Castonguay, D., de Figueiredo, C.M.H., Kowada, L.A.B., Patrão, C.S.R., Sasaki, D.
• Format: Article
• Language: English
• Subjects: Cycle graph; Direct product; Graph theory; Total coloring
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2023.113340

A k-total coloring of a graph G is an assignment of k colors to its elements (vertices and edges) so that adjacent or incident elements have different colors. The total chromatic number is the smallest integer k for which the graph G has a k-total coloring. Clearly, this number is at least Δ(G)+1, where Δ(G) is the maximum degree of G. When the lower bound is reached, the graph is said to be Type 1. In 2018, the direct product of cycle graphs Cm×Cn, for m=3p,5ℓ,8ℓ with p≥2 and ℓ≥1, and arbitrary n≥3, was proved to be Type 1 and suggested the conjecture that, except for C4×C4, the direct product of cycle graphs Cm×Cn with m,n≥3 is Type 1. We prove this conjecture and search further for sufficient conditions to ensure that the direct product of graphs is Type 1. We ask whether one factor being Type 1 is enough to ensure that the direct product also is a Type 1 graph. We prove that the direct product of a conformable regular graph with a regular graph is always conformable. We also prove that the direct product of a Type 1 graph with a bipartite graph is always Type 1.