Total colorings of product graphs (Q1743686): Difference between revisions

A proper total coloring of a graph \(G\) is an assignment of colors to vertices and edges of the graph, such that adjacent and incident elements receive different colors. The total chromatic number \(\chi^{\prime\prime}(G)\) of the graph \(G\) is the minimum number of colors needed for a proper total coloring. Clearly, if \(\Delta\) is the maximum degree of \(G\), then \(\Delta+1 \leq \chi^{\prime\prime}(G)\). The Behzad-Vizing total coloring conjecture asserts that for all graphs \(\chi^{\prime\prime}(G)=\Delta+1\) or \( \chi^{\prime\prime}(G)=\Delta+2\). The paper verifies the conjecture for various products of certain classes of graphs.