Total colorings of core-satellite, cocktail party and modular product graphs

Abstract

A total coloring of a graph G is a combination of vertex and edge colorings of G. In other words, is an assignment of colors to the elements of the graph G such that no two adjacent elements (vertices and edges) receive a same color. The total chromatic number of a graph G, denoted by χ00(G), is the minimum number of colors that suffice in a total coloring. Total coloring conjecture (TCC) was proposed independently by Behzad and Vizing that for any graph G, ∆(G) + 1 ≤ χ00(G) ≤ ∆(G) + 2, where ∆(G) is the maximum degree of G. In this paper, we prove TCC for Core Satellite graph, Cocktail Party graph, Modular product of paths and Shrikhande graph.