Back close

Total Coloring of Some Classes of Cayley Graphs on Non-Abelian Groups

Publication Type : Journal Article

Source : Symmetry 2022, 14, 2173.

Url :

Keywords : total coloring, symmetric group, Cayley graph, dihedral group, Kneser graph

Campus : Coimbatore

School : School of Engineering

Department : Mathematics

Year : 2022

Abstract : Total Coloring of a graph G is a type of graph coloring in which any two adjacent vertices, an edge, and its incident vertices or any two adjacent edges do not receive the same color. The minimum number of colors required for the total coloring of a graph is called the total chromatic number of the graph, denoted by χ′′(G). Mehdi Behzad and Vadim Vizing simultaneously worked on the total colorings and proposed the Total Coloring Conjecture (TCC). The conjecture states that the maximum number of colors required in a total coloring is Δ(G)+2, where Δ(G) is the maximum degree of the graph G. Graphs derived from the symmetric groups are robust graph structures used in interconnection networks and distributed computing. The TCC is still open for the circulant graphs. In this paper, we derive the upper bounds for χ′′(G) of some classes of Cayley graphs on non-abelian groups, typically Cayley graphs on the symmetric groups and dihedral groups. We also obtain the upper bounds of the total chromatic number of complements of Kneser graphs.

Cite this Research Publication : Prajnanaswaroopa S., Geetha J., Somasundaram K., Suksumran T., "Total Coloring of Some Classes of Cayley Graphs on Non-Abelian Groups", Symmetry 2022, 14, 2173.

Admissions Apply Now