Article ID Journal Published Year Pages File Type
4648141 Discrete Mathematics 2012 4 Pages PDF
Abstract

The total chromatic number of a graph GG, χT(G)χT(G), is the least number of colours sufficient to colour the vertices and edges of a graph such that no incident or adjacent elements (vertices or edges) receive the same colour. The Total Colouring Conjecture (TCC)   states that every simple graph GG has χT(G)≤Δ(G)+2χT(G)≤Δ(G)+2, and it is a challenging open problem in Graph Theory. For both split graphs and indifference graphs, the TCC holds, and χT(G)=Δ(G)+1χT(G)=Δ(G)+1 when Δ(G)Δ(G) is even. For a split-indifference graph GG with odd Δ(G)Δ(G), we give conditions for its total chromatic number to be Δ(G)+2Δ(G)+2, and we build a (Δ(G)+1)(Δ(G)+1)-total colouring otherwise. Also, we pose a conjecture for a class of graphs that generalizes split-indifference graphs.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,