Discrete Mathematics and Optimization Seminar
Sept. 15, 2008
Optimal colouring of the edges of the join of two regular graphs
Caterina De Simone
CNR, Rome
We prove that the edges of every graph G that is the join of two regular graphs can be coloured with Delta(G) colours. The proof yields a combinatorial algorithm to optimally colour the edges of this type of graphs. This is a joint work with Anna Galluccio