We consider the following conjecture: Let G be a k-regular simple graph with an even number n of vertices. If k >= n/2 then G is k-edge-colourable. We show that this conjecture is true for graphs that are join of two graphs and we provide a polynomial time algorithm for finding a k-edge-colouring of these graphs.
Edge colouring of regular graphs of large degree
De Simone C;Galluccio A
2007
Abstract
We consider the following conjecture: Let G be a k-regular simple graph with an even number n of vertices. If k >= n/2 then G is k-edge-colourable. We show that this conjecture is true for graphs that are join of two graphs and we provide a polynomial time algorithm for finding a k-edge-colouring of these graphs.File 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.
