Total colorings-a survey

Abstract

The smallest integer k needed for the assignment of k colors to the elements so that the coloring is proper (vertices and edges) is called the total chromatic number of a graph. Vizing [126] and Behzad [6, 7] conjectured that the total coloring can be done using at most $\Delta (G)+2$ colors, where $\Delta (G)$ is the maximum degree of G. It is not settled even for planar graphs. In this paper, we give a survey on the total coloring of graphs.

Keywords:

• Total coloring
• survey
• planar graph
• product graphs
• non-planar graphs

1. Introduction

Let G be a simple graph with vertex set V(G) and edge set E(G). An element of G is a vertex or an edge of G. The total coloring of a graph G is an assignment of colors to the vertices and edges such that no two incident or adjacent elements receive the same color. The total chromatic number of G, denoted by $\chi ″(G),$ is the least number of colors required for a total coloring. Clearly, $\chi ″(G)\ge \Delta (G)+1,$ where $\Delta (G)$ is the maximum degree of G.

Behzad [6, 7] and Vizing [126] independently posed a conjecture called Total Coloring Conjecture (TCC) which states that for any simple graph G, the total chromatic number is either $\Delta (G)+1$ or $\Delta (G)+2.$ Brualdi [11] and Alon [2] asked whether the total chromatic number of a graph G is at most $\Delta (G)+C$ for some absolute constant. In [92], Molloy and Reed gave a positive answer to the question. They gave a probabilistic approach to prove that for sufficiently large $\Delta (G),$ the total chromatic number is at most $\Delta (G)+C,$ where $C={10}^{26}.$ Their proof relies heavily on several applications of the Lovász Local Lemma [48]. They also suggested that by adding a few more intricacies to their proof and being a little more careful in the calculations, one can obtain C = 500. Still, this bound is much larger than the bound conjectured by Behzad and Vizing. If C = 2, then the problem becomes the total coloring conjecture. If C = 3, then the problem becomes weak total coloring conjecture (refer to Section 3.8). Murthy announced a proof for total coloring conjecture in his arXiv paper [93] using an algebraic approach called Combinatorial Nullstellensatz, given by Noga Alon.

If $\chi ″(G)=\Delta (G)+1$ then G is known as a type I graph and if ${\chi }^{″}(G)=\Delta (G)+2$ then G is a type II graph. In this paper, we present a comprehensive survey on total coloring. Yap [153] gave a nice survey on total colorings that covers the results till 1995. Therefore, our survey cover results from 1996 onwards. There are four sections in this paper. In the second section, we focus on the results of planar graphs. In [9], Borodin gave a survey of results on the total colorings of planar graphs up to 2009. There have been several improved results on planar graphs since then. Thus, we only present the results from 2010 onwards. For the earlier results, we refer the readers to the earlier two excellent surveys mentioned above. The third section of this paper consists of results on non-planar graphs. In the last section, we survey the results on the complexity aspects of total coloring.

2. Planar graphs and beyond

In this section, we consider the results related to planar graphs (graphs that have a plane embedding). Many of the results in total coloring of planar graphs are based on the maximum degree and the girth constraints.

One of the most yielding techniques on planar graphs is the Discharging Method. While one can say that the discharging method has been used in graph theory for more than 100 years, it came to prominence when it was used to prove the four color theorem by Appel and Hacken. Since then, the method has been applied to many types of problems (including graph embeddings and decompositions, spread of infections in networks, geometric problems, etc.). It is especially useful in planar graphs. An excellent guide to the method of discharging is given by Cranston and West [35].

A rough sketch of using the discharging method is as follows [100]:

Charging phase:

1. Assign initial charges to certain elements of a graph (vertices, edges, faces, etc.).

2. Compute the total charge assigned to the whole graph (for planar graphs typically using Euler’s formula).

Discharging phase:

1. Redistribute the charge in the graph according to a set of discharging rules.

2. Compute the total charge again (using the specific properties of the graph), and derive a conclusion.

A configuration in a graph G can be any structure in G (often a specified sort of subgraph). A configuration is reducible for a graph property Q if it cannot occur in a minimal graph not having property Q. The method of discharging is used to show that a set of reducible configurations is unavoidable in the class of graphs being discussed which establishes that the property Q cannot have a counterexample in the class. Let $d_G(v)$ or simply d(v) denote the degree (number of neighbors) of vertex v in G, and let d(G) denote the average of the vertex degrees in G. Degree charging is the assignment to each vertex v of an initial charge equal to d(v). In the following, we present the total coloring results on planar graphs.

The total coloring conjecture was verified for planar graphs with $\Delta (G)\le 5$ [72]. Sanders and Zhao [109] showed that every planar graph with $\Delta (G)\le 7$ is 9-total colorable. Yap [153] verified TCC for planar graphs with $\Delta (G)=8.$ In [73], Kowalik et al. proved that any planar graph with $\Delta (G)\ge 9$ is type I. Shen et al. [116] posed a conjecture on the total coloring of planar graphs, which states that “Planar graphs with $4\le \Delta (G)\le 8$ are $(\Delta (G)+1)$-total colorable”. Wang et al. [130] proved that for a planar graph G with maximum degree $\Delta (G)$ and girth g such that G has no cycles of length from g + 1 to $t,t>g,$ the total chromatic number is $\Delta (G)+1$ provided $(\Delta (G),g,t)\in \{(5,4,6),(4,4,17)\}$ or $\Delta (G)=3$ and $(g,t)\in \{(5,13),(6,11),(7,11),(8,10),(9,10)\},$ where each vertex is incident with at most one g-cycle. For more details, we refer to the excellent survey by Borodin [9].

We present the survey on the total coloring of the planar graph with degree constraints. We divide the section into four subsections. First subsection deals with a maximum degree at least 6, the second with 7, and the third with a maximum degree at least 8. In the last subsection, we have given some results about the total coloring of some graphs embedded on different surfaces.

2.1. Planar graphs with $\Delta (G)\ge 6$

First, we start with results involving planar graphs with a maximum degree at least six. As far as we know, the first work on the total coloring with $\Delta (G)=6$ was given by Wang et al. [146]. They verified TCC for planar graphs without 4 cycles. Shen et al. improved the result by showing that the planar graph without 4-cycles is type I [116] with the reducible configuration shown in Figure 1. where the vertices marked by ·are of degree 2 in the graph G. Sun et al. [120] proved that every planar graph G with maximum degree 6 is totally 8-colorable if no two triangles in G share a common edge (which implies that every vertex v in G is incident with at most $\lfloor \frac{d(v)}{2}\rfloor$ triangles. Observe that if every vertex is missing either a 3-cycle or a 4-cycle, then no two triangles in G share a common edge). They also proved that a planar graph without adjacent triangles and without cycles of length k, $k\ge 5,$ is type I. Roussel [104] strengthened the result of [120] by showing that a planar graph G is total 8-colorable if every vertex v of G is missing some k_v-cycle for $k_v\in \{3,4,5,6,7,8\}.$ In 2017, Zhu and Xu [161] improved the result of Sun et al. [120] to show that TCC holds for planar graphs G with $\Delta (G)=6,$ provided G does not contain any subgraph isomorphic to a 4-fan.

Figure 1. Reducible configuration from [116].

A notion closely related to the total coloring of graphs is the list total coloring of graphs. Suppose that a set L(x) of colors, called a list of x, is assigned to each element $x\in V(G)\cup E(G).$ A total coloring $\varphi$ is called a total L-coloring of G, if $\varphi (x)\in L(x)$ for each element $x\in V(G)\cup E(G).$ If $|L(x)|=k$ for every $x\in V(G)\cup E(G),$ then a total L- coloring is called a list total k coloring, and we say that G is totally k-choosable and the minimum integer k for which G is total k-choosable is the total choosability of G.

Lu et al. [80], proved that for a planar graph with $\Delta (G)\ge 6,$ and without cycles of length 3 adjacent to cycles of length 5 satisfies ${\chi }_l^{\prime }\prime (G)\le \Delta (G)+2.$ TCC follows from this result.

Further improvements on the total coloring of the planar graph with $\Delta \ge 6$ are as follows. Zhang and Wang [154] showed that every planar graph with $\Delta \ge 6$ and without adjacent short cycles (a cycle of length at most 4) is $(\Delta +1)$-total-colorable. Hou et al. [65] proved that a planar graph G is type I if $\Delta (G)\ge 5$ and G contains neither 4-cycles nor 6-cycles or $\Delta (G)\ge 6$ and G contains neither 5-cycles nor 6-cycles. A chordal k-cycle is a k-cycle with at least one chord. In [148], Wu et al. improved the result of [65] by showing that a planar graph with maximum degree $\Delta (G)$ is M-totally colorable if it contains neither chordal 5-cycle nor chordal 6-cycle, where $M=\max \{7,\Delta (G)+1\}.$ Dong et al. [46] proved that a planar graph G where no 6-cycles has a chord satisfies TCC provided $\Delta (G)\ge 6.$ Li [77] verified TCC for planar graphs with maximum degree six, if for each vertex v, there is an integer $k_v\in \{3,4,5,6\}$ such that G has no k_v-cycle containing v.

For planar graph with $v_5^4+2(v_5^{5^{+}}+v_6^4)+3v_6^5+4v_6^{6^{+}}<24,$ Leidner [74] verified TCC, where $v_n^k$ is number of vertices of degree n which lie on k distinct 3-cycles for each $n,k\in N$ and k⁺ means k or more.

A graph is called claw-free graph if it does not contain $K_{1,3}$ as an induced subgraph. A claw-free planar graph has maximum degree at most 6. Liang [78] proved that a claw-free planar graph is 8-total colorable. Liu et al. [79] proved that a planar graph G is total $(\Delta (G)+2)$-choosable ($(\Delta (G)+2)$-total colorable) whenever (1) $\Delta (G)\ge 7$ and G has no adjacent triangles or (2) $\Delta (G)\ge 6$ and G has no intersecting triangles or (3) $\Delta (G)\ge 5$ and G has no adjacent triangles and G has no k-cycles for some integer $k\in \{5,6\}.$

2.2. Planar graphs with $\Delta (G)\ge 7$

We now list the results on the total coloring of the planar graph with a maximum degree at least 7. The first work on this direction is due to Sanders and Zhao [109].

Shen and Wang [117] showed that the planar graphs with maximum degree 7 and without 5-cycles are 8-totally colorable. Figure 2 shows the reducible configuration used in [117]. Chang et al. [24] proved that a planar graph G with maximum degree 7, with the additional property that for every vertex v, there is an integer $k_v\in \{3,4,5,6\}$ so that v is not incident with any k_v-cycle, is type I. Cai et al. [14], strengthened the result and proved that for a planar graph G with $\Delta (G)\ge 7,$ there is an integer $k_v\in \{3,4,5,6,7,8\}$ such that there is no k_v-cycle which contains v, is type I.

Figure 2. Reducible configurations from [117].

Wang and Wu [127] proved that a planar graph of maximum degree $\Delta (G)\ge 7$ is $(\Delta (G)+1)$-totally colorable if no 3-cycle has a common vertex with a 4-cycle or no 3-cycle is adjacent to a cycle of length less than 6. Bonamy [8] improved the result and showed that $\chi \prime {\prime }_l=\Delta (G)+1$ if no triangle adjacent to a C₄. Wang et al. [141] proved that a planar graph with $\Delta (G)\ge 7$ and any 4-cycle is not adjacent to an i-cycle for any $i\in \{3,4\},$ then $\chi \prime {\prime }_l(G)=\Delta (G)+1.$ In [128], Wang et al. proved that for any planar graph with maximum degree $\Delta (G)\ge 7$ and without intersecting 3-cycles (two cycles of length 3 are not incident with a common vertex), and without intersecting 5-cycles, the total chromatic number is $\Delta (G)+1$ [129]. Wu et al. [140] proved that for a planar graph with maximum degree at least 7 and without adjacent 4-cycles, the total chromatic number is $\Delta (G)+1.$ In [121], Tan proved that the total chromatic number of a planar graph G with $\Delta (G)\ge 7$ and G does not contain adjacent 5-cycles is $\Delta (G)+1.$

General 5-cycles contain the following cases: (1) 5-cycles; (2) three 3-cycles C₁, C₂ and C₃ with $E(C_1)\cap E(C_2)\cap E(C_3)\ne \varnothing .$ In W_n (the join $C_n\vee K_1,C_n=[v_1{v}_2\dots v_n]$), by inserting l vertices of degree 2 on each edge $v_i{v}_{i+1},i=1,2,\dots ,n$ with $v_{n+1}=v_1,$ the resulting graph is called an l-cycle subdivision of W_n. A k-cycle-subdivision of W_n is an l-cycle-subdivision of W_n with $0\le l\le k.$ In [119], Sun et al. proved that a planar graph with $\Delta (G)$ at least 7, without general 5-cycles and $1^{-}$-cycle subdivisions of W₃ has list total chromatic number $\Delta (G)+1.$

The total chromatic number of a planar graph with $\Delta (G)\ge 7$ and without chordal 6-cycles [131] and without chordal 7-cycles [13] is $\Delta (G)+1.$ Wang et al. [135] gave a modified proof of the main result in [131].

A cycle C of length k is called k-cycle, and if there is at least one edge $xy\in E(G)\backslash E(C)$ and $x,y\in V(C),$ the cycle C is called non-induced k-cycle. In [76], Dong et al. proved that a planar graph G with $\Delta (G)\ge 7$ and without non-induced 7-cycles, satisfies ${\chi }_l^{\prime }\prime \le \Delta (G)+2$ and hence satisfies TCC.

2.3. Planar graphs with $\Delta (G)\ge 8$

We now turn to the results on maximum degree at least 8. There are many works on planar graphs with maximum degree at least 8. Yap [153] verified the TCC for planar graphs with $\Delta (G)\ge 8.$

Roussel and Zhu [105] proved that for a planar graph G with maximum degree 8, $\chi ″(G)=9,$ if there is no k_x-cycle which contains x, where x is a vertex in G and $k_x\in \{3,4,5,6,7,8\}.$ This is an improvement over [67], which is for $k_x\in \{5,6\}.$ The reducible configurations used by Roussel and Zhu are given in Figure 3. Further, Wang et al. [139], strengthened the result and proved that for a planar graph with $\Delta (G)\ge 8,$ if for every vertex $v\in V,$ there exist two integers, $i_v,j_v\in \{3,4,5,6,7,8\}$ such that v is not incident with intersecting i_v-cycles and j_v-cycles, then the total chromatic number of G is $\Delta (G)+1.$ Wang et al. [134] showed that the total chromatic number of planar graphs with $\Delta (G)\ge 8$ is $\Delta (G)+1,$ if for every vertex $v\in V(G),$ there exists two integers $i_v,j_v\in \{3,4,5,6,7\}$ such that v is not incident with adjacent i_v-cycles and j_v- cycles. In [80], Lu et al. proved that the list total chromatic number of a planar graph with $\Delta (G)\ge 8$ and without cycles of length 3 adjacent to cycles of length 5 is $\Delta (G)+1.$

Figure 3. Reducible configuration from [105].

Xu and Wu [151] proved that if G is a planar graph with maximum degree at least 8 and every 7-cycle of G contains at most two chords, then G has a $(\Delta (G)+1)$-total-coloring. Wang et al. [143], considered planar graphs G with maximum degree $\Delta (G)\ge 8,$ and showed that if G contains no adjacent i, j-cycles with two chords for some $i,j\in \{5,6,7\},$ then G is total $(\Delta (G)+1)$-colorable. Chang et al. [25] proved that planar graphs with maximum degree at least 8 and without 5-cycles with two chords are $\Delta (G)+1$ total colorable.

In [15], Cai et al. proved that the planar graphs with maximum degree 8 and without intersecting chordal 4-cycles are 9-totally colorable. Xu et al. [152] proved that if G is a planar graph with maximum degree at least 8 and every 6-cycle of G contains at most one chord or any chordal 6-cycles are not adjacent, then G has a $(\Delta (G)+1)$-total coloring. In 2014, Wang et al. [138] showed that a planar graph with $\Delta (G)\ge 8$ and without adjacent cycles of size i and j, for some $3\le i\le j\le 5,$ is $(\Delta (G)+1)$-total colorable.

Later, Wang et al. [133] proved that a planar graph with $\Delta (G)\ge 8$ and if $v\in V(G)$ is not incident with chordal 6-cycle, or chordal 7-cycle or 2-chordal 5-cycle, then it is type I. This is a generalization of [138]. In the list version it was proved by Wang et a.l [137] that a planar graph G with $\Delta (G)\ge 8$ and without chordal 5-cycles have the list total chromatic number $\Delta (G)+1.$

In [27], Chang et al. proved that a planar graph with maximum degree at most 8 is 9-total colorable if for every vertex v, v is incident with at most $d(v)-2\lfloor \frac{d(v)}{5}\rfloor$ triangles. This is a generalisation of [15] and [25].

Chang et al. [26] showed that “If G is an F₅-free planar graph with $\Delta (G)\ge 8,$ then $\chi ″(G)=\Delta (G)+1$”, where $F_n=K_1\vee P_n.$

2.4. Other graph embeddings

There are some other classes of graphs that are similar to planar graphs. In this subsection, we show the review results of other graph embeddings.

A maximal planar graph is a planar graph to which no new edges can be added without violating planarity. A recursive maximal planar graph is a special maximal planar graph, which can be obtained from K₄, by embedding a 3-vertex in a triangular face continuously (embedding a 3-vertex in a triangular face means: adding a new vertex in the face, and then connecting the vertex to each vertex of the triangular face with one edge). Zhou et al. [160] proved that TCC holds for recursive maximal planar graphs. In particular, they showed that (2, 2)-recursive maximal planar graphs are type I. Also, they proposed linear time algorithms for total coloring of recursive maximal planar graphs and (2, 2)-recursive maximal planar graphs, respectively. A Dumbbell maximal planar graph is a planar graph obtained from extending 3-wheel and 4-wheel operations. Zhou et al. [160] studied the structural properties of the dumbbel planar graph. Also, they proved that TCC holds for dumbbell maximal planar graphs.

A graph is called 1-planar if every edge is crossed by at most one other edge. The following are some results on total coloring of 1-planar graphs. Zhang et al. [159] proved that each 1-planar graph with $\Delta (G)\ge 16$ is $(\Delta (G)+2)$-total colorable and $(\Delta (G)+1)$-total colorable if $\Delta (G)\ge 21.$ Czap [36] studied the 1-planar graphs and gave some upper bound for the total chromatic number. He showed that a 1-planar graph with $\Delta (G)\ge 10$ satisfies TCC if $\chi (G)\le 4.$ He also proved that if G is a 1-planar graph without adjacent triangles and with $\Delta (G)\ge 8,$ then $\chi ″(G)\le \Delta (G)+3$ and if $\chi (G)\le 4,$ then $\chi ″(G)\le \Delta (G)+2.$ Zhang et al. [157] showed that for a 1-planar graph G, if $\Delta (G)\ge 13,$ then $\chi ″(G)\le \Delta (G)+2.$ In [118], Sun et al. proved that every 1-planar graph G is totally $(\Delta (G)+2)$-colorable if $\Delta (G)\ge 9$ and $g(G)\ge 4,$ or $\Delta (G)\ge 7$ and $g(G)\ge 5,$ where g(G) is girth of G.

An outerplanar graph is a planar graph that has a plane embedding such that all vertices lie on the boundary of the outer face. An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing total coloring of G is denoted by $\chi \prime {\prime }_a(G).$ In [145], Y. Wang and W. Wang characterized the adjacent vertex distinguishing total chromatic number of outerplanar graphs. They proved that if G is an outerplanar graph with $\Delta (G)\ge 3,$ then $\chi \prime {\prime }_a(G)\le \Delta (G)+2$ and so the TCC is satisfied. They also proved that if G is an outerplanar graph with $\Delta (G)\ge 3$ and without adjacent vertices of maximum degree, then $\chi \prime {\prime }_a(G)=\Delta (G)+1$ and hence G is a type I graph.

A graph is pseudo-outerplanar if each of its blocks has an embedding in the plane so that the vertices lie on a fixed circle and the edges lie inside the disk of this circle, each crossing at most one another. In [158], Zhang and Liu verified TCC for pseudo-outerplanar graphs and proved that the total chromatic number of every outerplanar graph with $\Delta (G)\ge 5$ is $\Delta (G)+1.$ A graph G is outer-1-planar with near-independent crossings (Nicop) if G is outer- 1-planar (also called pseudo-outerplanar) and $|M_G(c_1)\cap M_G(c_2)|\le 1$ for any two distinct crossings c₁ and c₂ in G. As an improvement of [158], Zhang [156] proved that the total chromatic number of every outer-1-planar graph with near-independent crossings and with maximum degree 4 is exactly 5. Zhang [155] proved that every pseudo-outerplanar graph with $\Delta (G)\ge 5$ is totally $(\Delta (G)+1)$-choosable and hence the total chromatic number also has this as the upper bound.

Similar to planar graphs, there is another type of graph called toroidal graphs, which are embedding of graphs on a torus such that there are no crossing edges. A graph is 1-toroidal if it can be drawn in torus such that every edge crosses at most one other edge. Wang [144] proved that if G is a 1-toroidal graph with maximum degree $\Delta (G)\ge 11$ and without adjacent triangles, then G has a total coloring with at most $\Delta (G)+2$ colors.

Now, we turn to some other surfaces. The Euler characteristic χ was classically defined for the surfaces of polyhedra, according to the formula $\chi =V-E+F,$ where V, E and F are, respectively, the numbers of vertices, edges and faces. In [66], Hou et al. proved that a graph G embedded in a surface ∑ of Euler characteristic $\chi (\sum )\ge 0$ with $\Delta (G)\ge 10$ is type I. Wang et al. [142] extended the result to $\Delta (G)\ge 9.$ Wang et al. [136] verified TCC for a graph G embedded in a surface ∑ of Euler characteristic $\chi (\sum )\ge 0$ and $\Delta (G)\ge 7.$ Wang et al. [132] proved if a graph G can be embedded in a surface of Euler characteristic $\chi \ge 0,$ with $\Delta (G)\ge 7$ and contains no 3-cycles adjacent to 4-cycles then it is type I.

3. Non-planar graphs

3.1. Circulant graphs

For a sequence of positive integers $1\le d_1<d_2<\dots <d_l\le \lfloor \frac{n}{2}\rfloor ,$ the circulant graph $G=C_n(d_1,d_2,\dots ,d_l)$ has vertex set $V=Z_n=\{0,1,2,\dots ,n-1\},$ two vertices x and y being adjacent if and only if $x=(y\pm d_i)\hspace{1em}\mathrm{mod}n$ for some $i,1\le i\le l.$

Khennoufa and Togni [71] studied the total colorings of circulant graphs and proved that 4-regular circulant graphs $G=C_{5p}(1,k)$ and $C_{6p}(1,k)$ are type I graphs for any positive integer p and $k<\frac{5p}{2}$ with $k\equiv 2\hspace{1em}\mathrm{mod}5$ or $k\equiv 3\hspace{1em}\mathrm{mod}5$ and $p\ge 3$ and $k<3p$ with $k\equiv 1\hspace{1em}\mathrm{mod}3$ or $k\equiv 2\hspace{1em}\mathrm{mod}3,$ respectively. Nigro et al. [97, 98] improved the results by proving that the circulant graph $C_n(2k,3)$ is type I for each $k\ge 1$ and $n=(8\mu +6\lambda )k,$ for non-negative integers μ and λ. In particular they proved that $C_{3n}(1,3)$ is type I, except for $C_{12}(1,3),$ which is type II. Navaneeth et al. [96] improved these results and obtained the total chromatic number for some classes of four regular circulant graphs. They proved that the circulant graphs $C_{5p}(a,b),$ where p ≥ 1,a,b ≡ 0 mod 5, are type I. Also they proved that $C_{6p}(a,b)$ where $a,b\cancel{\equiv }0$ mod 3 is type I, if p is even and $C_{6p}(a,b)$ where $a,b\cancel{\equiv }0$ mod 3 is type I, if p is odd and gcd $(a,b)=1.$

A graph is a power of cycle, denoted $C_n^k,$ n and k are integers, $1\le k<\lfloor \frac{n}{2}\rfloor ,$ if $V(C_n^k)=\{v_0,v_1,\dots ,v_{n-1}\}$ and $E(C_n^k)=E^1\cup E^2\cup \dots \cup E^k,$ where $E^i=\{e_0^i,e_1^i,\dots ,e_{n-1}^i\}$ and $e_j^i=(v_j,v_{(j+i)\text{mod}n})$ and $0\le j\le n-1,$ and $1\le i\le k.$

Campos and de Mello [18] proved that $C_n^2,n\ne 7,$ is type I and $C_7^2$ is type II. They [20] verified the TCC for powers of cycles $C_n^k,n$ even and $2<k<\frac{n}{2}$ and also showed that one can obtain a $(\Delta (G)+2)$-total coloring for these graphs in polynomial time. They also proved that $C_n^k$ with $n\equiv 0\hspace{1em}\mathrm{mod}(\Delta (C_n^k)+1)$ are type I, and they proposed the following conjecture.

Conjecture 1. Let $G=C_n^k$, with $2\le k<\lfloor \frac{n}{2}\rfloor$. Then, $$\chi ″(G)=\{\begin{array}{cc}\Delta (G)+2,\hfill & \mathrm{ }\text{if}\mathrm{ }k>\frac{n}{3}-1\text{and}\mathrm{ }n\text{is odd}\hfill \\ \Delta (G)+1\hfill & \mathrm{ }\text{otherwise}.\hfill \end{array}$$

Geetha et al. [55] proved this conjecture for certain values of n and k. They also verified TCC for the complement of powers of cycles ${\overline{C}}_n^k.$ In particular, they proved that ${\overline{C}}_n^2$ is type II for $n\le 8.$ Zorzi et al. [163] proved the conjecture for particular cases in even-power of cycle graphs. They proved that every $C_n^k$ with even $k\ge 2$ and $n\ge 4k^2+2k$ is type I. The same research group [164] proved the Campos and Mello’s conjecture for all $C_n^k$ graphs with $k\in \{3,4\}.$ A Cayley graph is a graph defined on a group H with respect to a symmetric generating set $S\subset H.$ The vertices of a Cayley graph are the elements of the group, and two vertices x and y in the graph are adjacent if and only if x = ys for some $s\in S.$ Prajnanaswaroopa et al. [102] verified the total coloring conjecture for certain classes of Cayley graphs on non-abelian groups, such as the symmetric and Dihedral groups.

In the following section, we look at graph products and papers on total coloring of product graphs.

3.2. Product graphs

Graph products were first defined by Sabidussi [107] and Vizing [125]. A lot of work has been done on various topics related to graph products, but on the other hand, there are still many questions open. There are four standard graph products, namely, $\mathit{Cartesian}\mathit{product}$ ($G\square H$), $\mathit{direct}\mathit{product}$ (G × H), $\mathit{strong}\mathit{product}$ ($G⊠H$) and lexicographic product ($G°H$). In [107], these products have been widely discussed with significant applications. The vertex sets of these products are same: $V(G)\times V(H).$ The edge sets are $E(G\square H)=\{((g,h),(g\prime ,h\prime ))|g=g\prime ,hh\prime \in E(H),\text{or}gg\prime \in E(G),h=h\prime \},$ $E(G\times H)=\{((g,h),(g\prime ,h\prime ))|gg\prime \in E(G)\text{and}hh\prime \in E(H)\},$ $E(G⊠H)=E(G\square H)\cup E(G\times H)$ and $E(G°H)=\{((g,h),(g\prime ,h\prime ))|g=g\prime ,hh\prime \in E(H),\text{or}gg\prime \in E(G)\}.$

The first three products are commutative and the lexicographic product is associative but not commutative.

The total coloring conjecture was verified for the Cartesian product of two graphs if the two graphs satisfy TCC. Seoud et al. [113, 114] determined the total chromatic number of the join of two paths, the Cartesian product of two paths, the Cartesian product of a path and a cycle, certain classes of the corona of two graphs, and the theta graphs. Kemnitz and Marangio [70] classified the Cartesian product of complete graphs $K_n\square K_m$ as type I if $n\ge m\ge 4,n\equiv 0\hspace{1em}\mathrm{mod}4$ or $n>m\ge 4,n\equiv 2\hspace{1em}\mathrm{mod}4,$ where n and m are even and as type II if n is even and m odd and $n>{(m-1)}^2.$ They also obtained the total chromatic number of the Cartesian product of two cycles $C_n\square C_m,K_n\square H$ and $C_n\square H,$ where H is a bipartite graph. Using the fact that if G is a regular graph with the adjacent vertex distinguishing chromatic index $\chi {\prime }_a=\Delta (G)+1$ then $\chi ″(G)=\Delta (G)+1.$ Baril et al. [4] proved that $K_n\square K_m$ is type I if $m\mathrm{ }\text{and}\mathrm{ }n$ are even. Still, there are cases of these products of complete graphs which are not classified as type I or type II. The equitable total chromatic number of a graph G is the smallest integer k for which G has a k-total coloring such that the number of vertices and edges colored with each color differs by at most one. Chunling et al. [34] improved the results of Seoud et al. [114] and Kemnitz et al. [70] by showing that the Cartesian product of two cycles C_m and $C_n,m,n\ge 3$ have equitable total 5-coloring. That is, $C_n\square C_m$ is type I. Zmazek and $\check{\mathrm{Z}}$ erovnik [162] proved that if TCC holds for graphs G and H, then it holds for the Cartesian product $G\square H.$ They also proved that if the factor with the largest vertex degree is of type I, then the product is also of type I.

There are only a few results proved on the total colorings of the other three product graphs. Prnaver and Zmazek [103] verified the conjecture for the direct product of a path and any graph G with $\chi \prime (G)=\Delta (G).$ Also, they proved that $G\times P_n$ satisfies TCC if G is type I.

Geetha and Somasundaram [54] proved that the direct product of two even complete graphs is type I, and the direct product of two cycles C_m and C_n are type I for certain values of m and n. They also proved that if $K_2⊠H$ ($K_2°H$) satisfies TCC, then $G⊠H$ ($G°H$) satisfies TCC, where G is any bipartite graph. Mackeigan and Janssen [87] proved that if $G\times K_2$ is type I, then G × H is type I for any bipartite graph H. Also, they proved that if n or $m,n,m\ge 3$ is even then $K_m\times K_n$ is type I. Castonguay et al. [22] improved the above result by proving the graph $K_m\times K_n$ is type I when both m and n are odd numbers. This settled the long standing problem on type I coloring of $K_m\times K_n$ except when $m=n=2.$

Mohan et al. [90] proved that the corona product of two graphs G and H is always type I, provided G is total colorable and H is either a cycle, a complete graph or a bipartite graph. Furmańczyk and Zuazua [52] proved that the equitable total chromatic number of corona product of two cubic graphs is $\Delta (G°H)+1.$ As a direct consequence, they proved that all coronas of cubic graphs are of type I. Vignesh et al. [123] settled the conjecture for all type of corona products by proving that the three types of corona products (vertex, edge, and neighborhood) of graphs are type I.

Sandhiya et al. [110] proved the TCC for certain classes of lexicographic product of graph. The deleted lexicographic product of two graphs G and H, denoted by D_lex (G, H), is a graph with the vertex set $V(G)\times V(H)$ and the edge set $\{((g,h),(g\prime ,h\prime )):(g,g\prime )\in E(G)$ and $h\ne h\prime ,$ or $(h,h\prime )\in E(H)$ and $g=g\prime \}.$ Similar to lexicographic product, $D_{\mathit{lex}}(G,H)$ and $D_{\mathit{lex}}(H,G)$ are not necessarily isomorphic. Vignesh et al. [122] proved that if G is a bipartite graph and H is any total colorable graph then $G°H$ is also total colorable. They further show that for any class I graph G and any graph H with at least 3 vertices, $D_{\mathit{lex}}(G,H)$ is total colorable. In particular, if H is class I then $D_{\mathit{lex}}(G,H)$ is also type I. In [124], they also prove the total coloring conjecture for Core Satellite graph, Cocktail Party graph, Modular product of paths and Shrikhande graph.

In the next section, we present the results on Sierpi $\acute{\mathrm{n}}$ ski graphs.

3.3. Sierpiński graphs

Sierpi $\acute{\mathrm{n}}$ ski graphs S(n, k), were defined by Klav $\check{\mathrm{z}}$ ar and Milutinovi $\acute{\mathrm{c}}$ [106]. The generalized Sierpi $\acute{\mathrm{n}}$ ski graph of G of dimension n denoted by S(n, G) was introduced by Gravier et al. [59] on the vertex set ${\{1,2,\dots ,k\}}^n.$ Two different vertices $u=(u_1,u_2,\dots ,u_n)$ and $v=(v_1,v_2,\dots ,v_n)$ are adjacent if and only if there exists an $h\in \{1,2,\dots ,n\}$ such that

1. u_t = v_t for $t=1,2,\dots ,h-1;$

2. $u_h\ne v_h;$ and

3. $u_t=v_h\mathrm{ }\text{and}\mathrm{ }{v}_t=u_h$ for $t=h+1,\dots ,n.$

Sierpi $\acute{\mathrm{n}}$ ski graphs are nothing but taking G as the complete graph K_k. Sierpi $\acute{\mathrm{n}}$ ski gasket graphs S_n were introduced by Scorer, Grundy and Smith [112]. The graph S_n is obtained from the Sierpi $\acute{\mathrm{n}}$ ski graphs $S(n,3)$ by contracting every edge of $S(n,3)$ that lies in no triangle. Jakovac and Klav $\check{\mathrm{z}}$ ar [69] generalized the graphs $S(n,3)$ to Sierpi $\acute{\mathrm{n}}$ ski graphs S(n, k) for $k\ge 3$ and determined the total colorings of the Sierpi $\acute{\mathrm{n}}$ ski gasket graphs S_n. In particular they proved that for any $n\ge 2$ and any odd $k\ge 3,$ S(n, k) and $S(n,4)$ are type I graphs. For the even values of $k\ge 6,$ they believed that S(n, k) is always type II and hence they proposed a conjecture that S(n, k) is type II. After three years, Hinz and Parisse [64] disproved the conjecture based on the canonical total colorings. Also, they proved that the Hanoi graphs $H_p^n$ are type I graphs. Geetha and Somasundaram [53] considered the generalized Sierpi $\acute{\mathrm{n}}$ ski graphs S(n, G) and proved that S(n, G) is type I for certain classes of G.

3.4. Chordal graphs

Chordal graphs are graphs in which every induced cycle is a 3-cycle. They form a very important class of graphs due to the fact that they have good algorithmic properties. The TCC is verified for several subfamilies of chordal graphs like interval graphs, split graphs and strongly chordal graphs. A graph G is called a split graph if its vertex set can be partitioned into two subsets U and V such that U induces a clique and V is an independent set in G. A color diagram $\mathcal{C}=\{R_1,R_2,\dots ,R_k\}$ of frame $d=(d_1,d_2,\dots ,d_k)$ is an ordered set of color arrays, where color array $R_i=\{c_{i,1},c_{i,2},\dots ,c_{i,d_i}\},$ of length d_i, consists of distinct colors for all $1\le i\le k.$ In [30], Chen et al. proved that the split graphs satisfy TCC. They also proved that if G is a split graph with $\Delta (G)$ even, then G is type I. They extensively used the concept of the color diagram to prove these results. Campos et al. [17] gave conditions for the split-indifference graph G to be type II and constructed a $\Delta (G)+1$-total colorings for the remaining. Hilton [61] proved the following (it is known as Hilton’s condition): Let G be a simple graph with an even number of vertices. If G has a universal vertex, then G is type II if and only if $\left|E(\overline{G})\right|+\alpha (\overline{G})<\frac{|V(G)|}{2},$ where $\alpha (\overline{G})$ is the cardinality of a maximum independent set of edges of $\overline{G}.$

Three-clique graphs are generalizations of the split-indifference graphs. Campos et al. [17] proposed a conjecture based on Hilton’s condition.

Conjecture 2

A 3-clique graph is type II if and only if it satisfies Hilton’s condition.

A graph is dually chordal if it is the clique graph of a chordal graph. The class of dually chordal graphs generalizes known subclasses of chordal graphs such as doubly chordal graphs, strongly chordal graphs, interval graphs, and indifference graphs. Figueiredo et al. [43] proved that TCC holds for dually chordal graphs. A pullback from G to $G\prime$ is a function $f:V(G)\to V(G\prime ),$ such that: (i) f is a homomorphism and (ii) f is injective when restricted to the neighborhood of $x,\forall x\in V(G).$ Based on this pullback method, they proved that if $\Delta (G)$ is even, then G is type I. Let X be a family of sets. If any subfamily of pairwise intersecting sets has a nonempty intersection, then this property is called the Helly property of X. A graph is neighborhood-Helly when the set $\{N(v):v\in V(G)\}$ satisfies the Helly property. A characterization of dually chordal graphs says that G is dually chordal if and only if G is neighborhood-Helly and G² is chordal. It is proved that [43] TCC holds for neighborhood-Helly graphs G such that G² is perfect. They also proposed the following problem, which is still open:

Determine the largest graph class for which all its odd maximum degree graphs are class I and for which all its even maximum degree graphs are type I.

3.5. Multipartite graphs

Graph amalgamation [3] is one of the powerful techniques for various graph problems. A graph H is an amalgamation of a graph G if there exists a function $\varphi$ called an amalgamation function from V(G) onto V(H) and a bijection $\varphi \prime :E(G)\to E(H)$ such that e joining u and v is in E(G) if and only if $\varphi \prime (e)$ joining $\varphi (u)$ and $\varphi (v)$ is in E(H). Total coloring conjecture was verified for some classes of multipartite graphs using the amalgamation technique.

Dong and Yap [47] proved that the complete p-partite graph $K=K(r_1,r_2,\dots ,r_p)$ is of type I if $r_2\le r_3-2$ and $|V(K)|=2n,r_1\le r_2\le \dots \le r_p.$ Deficiency of a graph G to be def $(G)=\sum _{v\in V(G)}(\Delta (G)-d(v)).$ Dalal and Rodger [39] proved that $K=K(r_1,\dots ,r_5)$ is type II if and only if $|V(K)|=0$ (mod 2) and def(K) is less than the number of parts in K of odd size. Dalal et al. [40] proved that the complete p-partite graph $K=K(r_1,r_2,\dots ,r_p)$ is type I if and only if $K\ne K_{r,r}$ and if K has an even number of vertices then def(K) is at least the number of parts of odd size. Using the graph amalgamations technique, they showed that all complete multipartite graphs of the form $K(r,r,\dots ,r+1)$ are type I.

Chen et al. [29] proved that an $(n-2)$-regular equi-bipartite graph $K_{n,n}-E(J)$ is type I if and only if J contains a 4-cycle. Campos and de Mello [19] determined the total chromatic number of some bipartite graphs like grids, near-ladders and k-dimensional cubes. A graph is said to be complete r-partite p-balanced if its vertex set can be partitioned into r independent sets; that is, no two vertices in the same part are adjacent; there is an edge between any two vertices of different independent sets; and the cardinalities of the independent sets are equal. de Silva et al. [38] improved the bound given by Fu [51], when r and p are odd, by exhibiting an equitable $\Delta (G)+1$-total coloring for these graphs. Later the same authors [37] proved that the equitable total chromatic number of $K_{r\times p}$ is $\Delta (G)+1$ for r and p even $(r\ge 4);$ and for r odd and p even. Also, they proved that all graphs of three infinite classes of tripartite complete non-balanced graphs have equitable total coloring with $\Delta (G)+1$ colors. Since they prove the equitable total coloring with $\Delta (G)+1$ colors, we can see that these graphs are type I graphs.

Given a bipartite graph $G=(X,Y,E),$ a chain ordering of X is an ordering $\sigma (X)=(x_1,x_2,\dots ,x_n)$ such that the neighborhoods of the vertices of X form a chain, that is, $N(x_1)\subseteq N(x_2)\subseteq \dots \subseteq N(x_n).$ A bipartite graph $G(X,Y,E)$ is said to be a chain graph if there exists a chain ordering of X. For a bipartite graph, a convex ordering of set X is a linear ordering $\sigma (X)=(x_1,x_2,\dots ,x_n)$ such that for every vertex y in Y, neighbors of y are consecutive vertices in $\sigma (X).$ If there exist convex orderings for both X and Y, simultaneously, then the bipartite graph is called biconvex. Panda et al. [99] gave a sufficient condition for a bipartite biconvex graph G to be type I. Also, they proved that the total coloring conjecture holds for the central graph of any graph.

3.6. Cubic graphs

Dantas et al. [42] proved that for each integer $k\ge 2,$ there exists an integer N(k) such that, for any $n\ge N(k),$ the generalized Petersen graph G(n, k) has total chromatic number 4.

A graph is called subcubic graph if $\Delta (G)\le 3.$ Feng and Lin [49] gave a constructive proof for the total coloring of a subcubic graph. Sethuraman and Velankanni [115] proved that the cube connected paths and a class of subcubic graphs having the property that the vertices are covered by independent triangles are type I.

Snarks are cyclically 4-edge-connected cubic graphs that do not allow a 3-edge coloring. Cavicchiolic et al. [23] proved that all the snarks of order less than 30 are of type I (this was proved with the aid of a computer). Also, they proposed an open problem “find (if any) the smallest snark (with respect to the order) which is of type II”. Motivated by that question, Campos et al. [16] proved that all graphs in three infinite families of snarks, the Flower Snarks, the Goldberg Snarks, and the Twisted Goldberg Snarks are type I. They gave recursive procedures to construct total colorings that use 4 colors in each case. Also, they proposed an open problem that all snarks are type I. Sasaki et al. [111] proved that the total chromatic number of some classes of Snarks like, Loupekhine, Goldberg snarksboth and Blanuša’s families of graphs is 4. They observed that the total chromatic number seems to have no relation with the chromatic index for a cubic graph of cyclic-edge-connectivity less than 4. Also, they proposed the following questions:

1. What is the smallest type II cubic graph without a square?

2. What is the smallest type II snark?

Brinkmann et al. [10] considered the problems posed by Campos et al. [16] and Sasaki el al. [111] and showed that there exist type II snarks for each even order $n\ge 40.$ They gave a computer search for which all the cubic graphs with girth 5 and up to 32 vertices are type I. Also, they proposed the following questions:

1. Does there exist a type II snark of order less than 40? (The only possible orders for which the existence is not yet known are 36 and 38.)

2. What is the smallest type II cubic graph with girth at least 5?

3. Is there a girth g so that all cubic graphs with girth at least g are type I?

Goņcalves [58] answered the above questions partially by proving all members of an infinite family of snarks obtained by the Superposition operation of the Petersen graph and all Blowup snarks are type I.

3.7. Graphs with degree constraints

Being a very difficult conjecture, it makes sense to prove the conjecture either for known classes of graphs or graphs with some degree constraints. Hilton and Hind [62] showed that TCC holds for the graphs G having $\Delta (G)\ge \frac{3}{4}|V(G)|.$ Chetwynd et al. [32] gave a necessary and sufficient condition for $\chi ″(G)=\Delta (G)+1,$ if G is odd order and regular of degree $d\ge \frac{1}{3}\sqrt{7}|V(G)|.$

Deficiency of a graph G to be def $(G)=\sum _{v\in V(G)}(\Delta (G)-d(v)).$ A graph G is said to be conformable if G has a vertex colouring that uses $\Delta (G)+1$ colours with def $(G)>n,$ where n is the number of colour classes with parity different from $|V(G)|.$ Chew [33] improved the previous result (Chetwynd et al. [32]) for $d\ge [\frac{(\sqrt{37}-1)}{6}]|V(G)|.$ He proved that for any regular graph G of odd order and with $d\ge [\frac{(\sqrt{37}-1)}{6}]|V(G)|,$ G is type I if and only if G is conformable; otherwise type II. Chang et al. [28] proved that every graph G with $\Delta (G)=6$ and mad $(G)\le \frac{23}{5}$ admits an 8-total-coloring, where mad(G) denote the maximum average degree of the graph G.

Xie and He [149] showed that if G is a regular graph of even order and $\delta (G)\ge \frac{2}{3}|V(G)|+\frac{23}{6},$ then $\chi ″(G)\le \Delta (G)+2.$ Later, Xie and Yang [150] proved the same result for the regular graph of odd order. Combining these two results, we conclude that if G is a regular graph with $\delta (G)\ge \frac{2}{3}|V(G)|+\frac{23}{6}$ then G satisfies TCC. In [84] Machado and de Figueiredo proved that every non-complete {square, unichord} -free graph of maximum degree at least 4 is type I. Also, they proved that any {square, unichord} -free graph is total colorable. Using graph decompositions, the same authors [83] proved that the non-complete {square, unichord} -free graphs of maximum degree 3 are type I.

A graph is said to be s-degenerate for an integer $s\ge 1$ if it can be reduced to a trivial graph by successive removal of vertices with degree $\le s.$ For example, every planar graph is 5-degenerate. Isobe et al. [68] proved that an s-degenerate graph G admits a total coloring with $\Delta (G)+1$ colors if the maximum degree $\Delta (G)\ge 4s+3.$ The proof is based on Vizing’s and K $\stackrel{..}{\mathrm{o}}$ nig’s theorems on edge colorings. Further, they gave a linear time algorithm to find a total coloring of a graph G with minimum number of colors if G is a partial k-tree.

In [88], Meek and Scoot proved that for any graph G with treewidth at most k and $\Delta (G)\ge (k+2)2^{k+2}$ the total chromatic number is $\Delta (G)+1.$ Bruhn et al. [12] improved the result by proving that the graph G of treewidth $k\ge 3$ and $\Delta (G)\ge \frac{{(k+3)}^2}{2}$ is type I.

3.8. Other classes of graphs

Mycielski [95] constructed a very important graph, later it is called Mycielskian graph $\mu (G),$ to build a graph with a high chromatic number and a small clique number. Let G be a graph with vertex set $V^0=\{v_1^0,v_2^0,\dots ,v_n^0\}$ and edge set E⁰. Given an integer $m\ge 1,$ the m-Mycielskian of G, denoted by ${\mu }_m(G),$ is the graph with vertex set $V^0\cup V^1\cup \dots \cup V^m\cup \left\{u\right\},$ where $V^i=\{v_j^i:v_j^0\in V^0\}$ is the i^th distinct copy of V⁰ for $i=1,2,\dots ,m,$ and the edge set $E^0\cup ({\cup }_{i=0}^{m-1}\{v_j^i{v}_j^{i+1}:v_j^0{v}_j{\prime }^0\in E^0\})\cup \{v_j^{m}u:v_j^m\in V^m\}.$ Chen et al. [31] showed that the generalized Mycielski graphs satisfy TCC. Also they proved the total chromatic number of generalized Mycielski graphs ${\mu }_m(G)$ is $\Delta ({\mu }_m(G))+1$ if $\Delta (G)\le \frac{|V(G)|-1}{2}.$

A graph G is prismatic if for every triangle T, every vertex not in T has exactly one neighbor in T. Prismatic graphs are a class of claw-free graphs. Mohan and Somasundaram [89] proved that the prismatic graphs are total colorable. Also, they proved that certain classes of prismatic graphs are type I. Quasi-line and inflated graphs are two well-known classes of claw-free graphs. Mohan et al. [91] verified TCC for the quasi-line and inflated graphs. Also, they showed type I coloring for some classes of quasi-line graphs and inflated graphs.

The Kneser Graphs K(n, k) are graphs consisting of $(\begin{array}{c}n\\ k\end{array})$ vertices which are k-subsets of an n element set, with two vertices adjacent whenever those correspond to disjoint sets. An odd graph O_n is the Kneser graph $K(2n-1,n-1).$ Prajnanaswaroopa et al. [101] have verified the TCC for all odd graphs by using Biggs standard representation, where an odd graph is decomposed into an independent set and a perfect matching. de Figueiredo et al. [44] used the same structural representations and proved that all odd graphs are type I.

Wang et al. [147] proved that the vertex distinguishing total chromatic number and the total chromatic number are the same for the graphs $P_n\vee P_n$ and $C_n\vee C_n.$ Li and Zhang [75] proved that the join of a complete inequibipartite graph $K_{n_1,n_2}$ and a path P_m is type I. Hilton et al. [63] determined the total chromatic numbers of graphs of the form $G_1+G_2,$ where G₁ and G₂ are graphs of maximum degree at most two. The line graph of G, denoted by L(G), has the set E(G) as its vertex set and two distinct vertices $e_1,e_2\in V(L(G))$ are adjacent if and only if they share a common vertex in G. Vignesh et al. [122] showed in a direct manner that for $n\le 4,L(K_n)$ is type I. They believed that $L(K_n)$ is always type I. Hence they proposed the following conjecture:

Conjecture 3

For any complete graph K_n, $\chi ″(L(K_n))=2n-3.$

The double graph D(G) of a given graph G is constructed by making two copies of G (including the initial edge set of each) and adding edges $((u,1),(v,2))$ and $((v,1),(u,2))$ for every edge uv of G. Vignesh et al. [122] proved that for any total colorable graph G, $$\chi ″(D(G))\{\begin{array}{cc}=\Delta (D(G))+1\hfill & \text{if}\mathrm{ }G\mathrm{ }\text{is}\mathrm{ }\text{type}\mathrm{ }\mathrm{I}\hfill \\ \le \Delta (D(G))+2\hfill & \text{if}\mathrm{ }G\mathrm{ }\text{is}\mathrm{ }\text{type}\mathrm{ }\text{II}.\hfill \end{array}$$

We know that middle graphs are subclasses of total graphs and superclasses of line graphs. Muthuramakrishnan and Jayaraman [94] obtained the total chromatic number for line, middle and total graphs of stars and bistars.

There is a weaker version of the total coloring conjecture (Weak TCC), namely, $\chi ″(G)\le \Delta (G)+3.$ Weak TCC is known to be true for 4-colorable graphs, and it was remain open for 5-colorable graphs. Basavaraju et al. [5] settled this case. It is know that $\chi ″(G)\ge \chi \prime (G)\ge \Delta (G).$ There are several graph classes are exist with a huge number of graphs with $\chi ″(G)>\chi \prime (G).$ For example, $K_{2n}$ is class I graph where as it is type II graph. In this context, in 1984, Goldberg [56] proposed a conjecture (Goldberg conjecture) which states that if $\chi \prime (G)\ge \Delta (G)+3,$ then $\chi ″(G)=\chi \prime (G).$ Recently, Yan Cao et al. [21] proved that if $\chi \prime (G)\ge \max \{\Delta (G)+2,|V(G)|+1\}$ then $\chi ″(G)=\chi \prime (G)$ .

In the next section, we look at the algorithmic aspects of TCC that has been discussed in the literature.

4. Algorithms

It is known [108] that the problem of finding a minimum total coloring of a graph is in general case NP-hard. In the same paper, Sanchez-Arroyo also proved that the problem is NP-complete even for cubic bipartite graphs. Evolutionary algorithms are a heuristic-based approach to solving problems that cannot be easily solved in polynomial time, such as classically NP-Hard problems. A genetic algorithm is an evolutionary algorithm. Many genetic algorithms were proposed for graph coloring problems. Dey et al. [45] proposed a genetic algorithm for total coloring problem. Luca Ferrarini and Stefano Gualandi [50] proposed Integer Linear Programming models for the total coloring and total matching problems. They have formulated the total coloring problem as a problem of finding the minimum number of total matchings that cover all the graph elements. Also, they presented column generation algorithm for the total coloring problem.

For general classes of graphs, the total coloring would be harder than edge colouring. Due to its complexity, several authors aim to find classes of graphs where there is a polynomial time algorithm for optimal total coloring. Bojarshinov [1] showed that the Behzad and Vizing conjecture holds for interval graphs. Also, he proved that every interval graph with even maximum degree can be totally colored in $\Delta (G)+1$ colors in time $O(|V(G)|+|E(G)|+{(\Delta (G))}^2).$ This is the first known polynomial time algorithm for total colorings. Golumbic [57] showed that a rooted path graph G is type I if $\Delta (G)$ is even; otherwise, it satisfies TCC. Also, he gave a greedy algorithm (very greedy neighborhood coloring algorithm) which takes $O(|V(G)|+|E(G)|)$ time. Panda et al. [99] proposed a linear time algorithm to compute the total chromatic number of chain graphs.

Chordal graphs are a subclass of the perfect graphs. We know that linear time algorithms exist for vertex colorings of chordal graphs. Yet, the complexity of total coloring is open for the class of chordal graphs. The complexity is known for interval graphs with even maximum degree [1], split graphs with even maximum degree [30] and dually chordal graphs with even maximum degree [43]. In [81], Machado and de Figueiredo proved that the total coloring of bipartite unichord-free graphs is NP-complete using the concept of separating class. Machado et al. [85] used a decomposition result to establish that every chordless graph of maximum degree $\Delta (G)\ge 3$ has total chromatic number $\Delta (G)+1$ and proved that this coloring can be obtained in time $O(|V(G){|}^3|E(G)|).$ Machado et al. [86] discussed the time complexity of {square, unichord} -free graphs and showed that the total coloring could be obtained in polynomial time. In this case, it is interesting to see that the edge coloring of these types of graphs are NP-complete.

Isobe et al. [68] proved that the total coloring problem for s-degenerate graph could be solved in time O(nlogn) for a fairly large class of graphs including all planar graphs with sufficiently large maximum degree. Further, they showed that the total coloring problem could be solved in linear time for partial k-trees with bounded k.

Dantas et al. [41] proved that the problem of deciding whether the equitable total chromatic number is 4 is NP-complete for bipartite cubic graphs. They also found one family of type I cubic graphs of girth 5 having equitable total chromatic number 4. There are several classes of graphs in which the complexity of total coloring are unknown. We conclude this survey with a listing of the computational complexity of edge and total colorings of certain classes of graphs in Table 1.

Table 1. Computational complexity of edge and total colorings.

Class of graphs	Edge coloring	Total coloring
Unichord free	NP-complete [82]	NP-complete [84]
Chordlesss	Polynomial [85]	Polynomial [85]
{ Square, unichord }-free, $\Delta \ge 4$	Polynomial [82]	Polynomial [83]
{ Square, unichord }-free, Δ = 3	NP-complete [82]	Polynomial [86]
{ triangle, unichord }-free	NP-complete [82]	NP-complete [84]
Bipartite unichord free	NP-complete [77]	NP-complete [81]
Interval graphs	Polynomial [1]	Polynomial [1]
Some classes of circulant graphs	Polynomial [60]	Polynomial [18, 20, 71]

5. Conclusions

Total coloring arises naturally since it is simply a mixture of vertex and edge colorings. The total coloring version of the maximum degree upper bound is a difficult problem that has eluded mathematicians for 60 years. The smallest integer k needed for the assignment of k colors to the elements so that the coloring is proper (vertices and edges) is called the total chromatic number of a graph. The statement of total coloring conjecture was independently introduced by Behzad [6, 7] and Vizing [126]. The conjecture states that the total coloring can be done using at most $\Delta (G)+2$ colors, where $\Delta (G)$ is the maximum degree of G.

In this survey, we extensively presented the results in total coloring in planar graphs and non-planar graphs. Also, we have cited several conjectures and open problems in this paper. Campos and de Mello proposed a conjecture on power of cycle graphs (refer Section 3.1). Campos et al. proposed a conjecture on chordal graphs (refer Section 3.4) and Vignesh et al. proposed a conjecture on line graph of a complete graph (refer Section 3.8). Classifications (type I or type II) are still open for several classes of graphs.

Acknowledgement

The authors wish to thank the anonymous reviewers for their valuable suggestions to improve the presentation of the paper.