Total coloring


List Total Colouring Conjecture ★★

Author(s): Borodin; Kostochka; Woodall

Conjecture   If $ G $ is the total graph of a multigraph, then $ \chi_\ell(G)=\chi(G) $.

Keywords: list coloring; Total coloring; total graphs

Total Colouring Conjecture ★★★

Author(s): Behzad

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.\]

Keywords: Total coloring

Syndicate content