Edge‐colouring of joins of regular graphs II

Edge‐colouring of joins of regular graphs II

0.00 Avg rating0 Votes
Article ID: iaor2013587
Volume: 25
Issue: 1
Start Page Number: 78
End Page Number: 90
Publication Date: Jan 2013
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: graphs
Abstract:

We prove that the edges of every even graph G=G 1+G 2 that is the join of two regular graphs G 1 and G 2 can be coloured with Δ(G) colours, whenever Δ(G)=Δ(G 1)+|V 2|. 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)‐edge‐colouring of this type of graphs.

Reviews

Required fields are marked *. Your email address will not be published.