Upper Bounds for the Total Chromatic Number of Join Graphs and Cobipartite Graphs
We concern ourselves with the combinatorial optimisation problem of determining a minimum total colouring of a graph G for the case wherein G is a join graph G G1 *G2 or a cobipartite graph G (V1 V2,E(G) We present algorithms for computing a feasible, not necessarily optimal, solution for this problem, providing the following upper bounds for the total chromatic numbers of these graphs (let ni |Vi| and i (Gi) for i {1,2} and ,kh,kh',kh' kh'(G) 6 max{n1,n2} 1+P(G1,G2) if G is a join graph, wherein P(G1,G2) =min{1+2+1,max{kh1,kh 2} kh(G)6max{n1,n2}+2(max{1 ,2}+1) if G is cobipartite, wherein i maxuVi dG[G(Vi)(u) for i {1,2} Our algorithm for the cobipartite graphs runs in polynomial time. Our algorithm for the join graphs runs in polynomial time if P(G1,G2) is replaced by 1 +2 +1 or if it can be computed in polynomial time. We also prove the Total Colouring Conjecture for some subclasses of join graphs, such as some joins of indifference (unitary interval) graphs.
ICORES