All direct product $C5 \times Kn$ graphs are Type~1

- 322050
Complete paper
Favorite this paper
How to cite this paper?
Abstract

A \textit{$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 $\Delta(G)+1$ (called Type~1) or $\Delta(G)+2$ (called Type~2), where $\Delta(G)$ is the maximum degree of $G$.  
In this paper, we establish that all the direct product $C_5 \times K_n$ graphs are Type~1, when $n$ is odd and not a multiple of 5, providing evidence for the conjecture that all $C_m \times K_n$ graphs are Type 1. 

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Institutions
  • 1 Universidade Federal de Goiás
  • 2 Universidade Federal do Rio de Janeiro (UFRJ)
  • 3 Universidade Federal do Rio de Janeiro
  • 4 Instituto Federal de Educação, Ciência e Tecnologia de Goiás
  • 5 Universidade do Estado do Rio de Janeiro - UERJ
Track
  • ST04 - Computer Graphics and Discrete Mathematics
Keywords
graph theory
direct product
total coloring