Edge-colouring of joins of regular graphs II |
| |
Authors: | Caterina De Simone Anna Galluccio |
| |
Affiliation: | 1. IASI-CNR, viale Manzoni 30, 00185, Rome, Italy
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|