A k-total coloring of a graph G = (V, E) is an assignment of k colors to the elements of G , such that adjacent or incident elements have different colors. Let ∆ be the maximum vertex degree of a graph G , the Total Coloring Conjecture states that every graph G is (∆ + 1), or (∆ + 2)-total colorable. In 1994, McDiarmid and Sánchez-Arroyo proved that the total coloring problem, asking whether a graph G is (∆ + 1)-total colorable, is NP-complete even when G is k -regular, k ≥ 3 and bipartite. In 1988, Chetwynd and Hilton defined conformable vertex coloring in the attempt to characterize the vertex coloring induced by a (∆ + 1)-total coloring. A (∆ + 1)-vertex coloring of a graph G is called conformable if the number of color classes of parity different from that of | V | is at most the deficiency def(G) =∑ v∈V (Δ − dG(v)) of G , where d G ( v) is the degree of a vertex v of V. Recently, it was proved that conformability is polynomial for maximum degree three graphs. However, the general time-complexity of conformability status remains unknown. Not every conformable coloring extends naturally to a (∆ + 1)-total coloring. One might ask when, or what properties a conformable vertex coloring should have to extend to a (∆ + 1)-total coloring. In this paper, we introduce the concept of strong conformable coloring a conformable coloring that extends to a total coloring. A strong conformable coloring is a conformable coloring with two additional properties. We show that each of these two properties is necessary in order to extend a conformable to a total coloring. Furthermore, we prove that a graph G is strong conformable if and only if G has a (∆ + 1)-total coloring. Consequently, we deliver the bad news that strong conformable vertex coloring problem is NP-complete even for bipartite k -regular graphs with k ≥ 3.

A k-total coloring of a graph G is an assignment of k colors to the vertices and edges (elements) of G so that adjacent or incident elements have different colors. The total chromatic number of G 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 ∆(G) + 1 or ∆(G) + 2, where ∆(G) is the maximum degree of G. Graphs with χ" (G) = ∆(G) + 1 are known as Type 1, and graphs with χ" (G) = ∆(G) + 2 are known as Type 2. In this work, we investigate the total coloring of circulant graphs. We establish that all members of three infinite families of 4-regular circulant graphs are Type 1, except for one graph which is Type 2. These results contribute to the conjecture proposed by Khennoufa and Togni in 2008, which states that, except for a finite number of Type 2, 4-regular circulant graphs are all Type 1.