A Combinatorial Algorithm to Optimally Colour the Edges of the Graphs That Are Join ofRegular Graphs

摘要

We prove that the edges of every even graph G = G_1 + G_2 that is the join of two regular graphs G_i = (V_i, E_i) can be coloured with △(G) colours, whenever △(G) = △(G_2) + |V(G_1)|. The proof of this result yields a combinatorial algorithm to optimally colour the edges of this type of graphs.