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
Edge-colouring of joins of regular graphs II
De Simone C;Galluccio A
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 · RegularFile in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
