Behzad, M.


Total Colouring Conjecture ★★★

Author(s): Behzad

\begin{conjecture} A total coloring of a graph $G = (V,E)$ is an assignment of colors to the vertices and the edges of $G$ such that every pair of adjacent vertices, every pair of adjacent edges and every vertex and incident edge pair, receive different colors. The total chromatic number of a graph $G$, $\chi''(G)$, equals the minimum number of colors needed in a total coloring of $G$. It is an old conjecture of Behzad that for every graph $G$, the total chromatic number equals the maximum degree of a vertex in $G$, $\Delta(G)$ plus one or two. In other words, \[\chi''(G)=\Delta(G)+1\ \ or \ \ \Delta(G)+2.\] \end{conjecture}

Keywords: Total coloring

Syndicate content