Data di Pubblicazione:
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
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
Tipologia CRIS:
01.01 Articolo in rivista
Elenco autori:
DE SIMONE, Caterina; Galluccio, Anna
Link alla scheda completa:
Pubblicato in: