Narrow Results

The total chromatic number ${\chi }^{″}(G)$ is the least number of colors needed to color the vertices and edges of a graph $G$ such that no incident or adjacent elements (vertices or edges) receive the same color. Behzad and Vizing proposed a well-known total coloring conjecture (TCC): ${\chi }^{″}(G)\le \mathrm{\Delta }(G)+2$, where $\mathrm{\Delta }(G)$ is the maximum degree of $G$. For the powers of cycles, Campos and de Mello proposed the following conjecture: Let $G=C_n^k$ denote the graphs of powers of cycles of order $n$ and length $k$ with $2\le k<\lfloor \frac{n}{2}\rfloor$. Then,

A total coloring of a graph is an assignment of colors to all the elements (vertices and edges) of the graph such that no two adjacent or incident elements receive the same color. A claw-free graph is a graph that does not have $K_{1,3}$ as an induced subgraph. Quasi-line and inflated graphs are two well-known classes of claw-free graphs. In this paper, we prove that the quasi-line and inflated graphs are totally colorable. In particular, we prove the tight bound of the total chromatic number of some classes of quasi-line graphs and inflated graphs.

A total coloring of a graph G is an assignment of colors to all the elements (vertices and edges) of the graph in such a way that no two adjacent or incident elements receive the same color. The Total Chromatic Number, ${\chi }^{″}(G)$ is the minimum number of colors which need to be assigned to obtain a total coloring of the graph $G$. The Total Coloring Conjecture made independently by Behzad and Vizing claims that, $\mathrm{\Delta }(G)+1\le {\chi }^{″}(G)\le \mathrm{\Delta }(G)+2$, where $\mathrm{\Delta }(G)$ represents the maximum degree of $G$. The lower bound is sharp, the upper bound remains to be proved. In this paper, we prove the Total Coloring Conjecture for certain classes of lexicographic product and deleted lexicographic product of graphs.

A total coloring of a graph $G$ is an assignment of colors to the elements of the graph $G$ such that no adjacent vertices and edges receive the same color. The total chromatic number of a graph $G$, denoted by ${\chi }^{″}(G)$, is the minimum number of colors that suffice in a total coloring. Behzad and Vizing conjectured that for any simple graph $G$, $\mathrm{\Delta }(G)+1\le {\chi }^{″}(G)\le \mathrm{\Delta }(G)+2$, where $\mathrm{\Delta }(G)$ is the maximum degree of $G$. In this paper, we prove the tight bound of the total coloring conjecture for the three types of corona products (vertex, edge and neighborhood) of graphs.

A total coloring of a graph is an assignment of colors to all the elements of the graph such that no two adjacent or incident elements receive the same color. A graph $G$ is prismatic, if for every triangle $T$, every vertex not in $T$ has exactly one neighbor in $T$. In this paper, we prove the total coloring conjecture (TCC) for prismatic graphs and the tight bound of the TCC for some classes of prismatic graphs.