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 = G_1*G_2 or a cobipartite graph G = (V_1 ∪ V_2, 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 n_i := |V_i| and □_i := □(G_i) for i ∈ {1,2} and □ ∈{Δ, X, X', X"}): X"(G) ≤ max{n_1, n_2} + 1 + P(G_1, G_2) if G is a join graph, wherein P(G_1, G_2) := min{Δ_1+Δ_2+1, max{X'_1, X"_2}}; X"(G) ≤ max{n_1,n_2} + 2(max{Δ_1~B,Δ_2~B}+ 1) if Gis cobipartite, wherein Δ_i~B:= max_(u∈V_i) d_(G[{partial deriv}_G(V_i)]) (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(G_1, G_2) 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.
展开▼
