Publication Date:
2011
abstract:
We prove that the edges of every even graph G = G1 + G2 that is the
join of two regular graphs G1 and G2 can be coloured with (G) colours, whenever
(G) = (G1)+|V2|. The proof of this result together with the results in De Simone
and Galluccio (J. Comb. Optim. 18:417-428, 2009) states that every even graph G
that is the join of two regular graphs is Class 1.
The proof yields an efficient combinatorial algorithm to find a (G)-edgecolouring
of this type of graphs.
Keywords Edge-colouring · Join · Regular
Iris type:
01.01 Articolo in rivista
List of contributors:
DE SIMONE, Caterina; Galluccio, Anna
Published in: