### G-97-04

# Optimal Edge-Colourings for a Class of Planar Multigraphs

## Odile Marcotte

Let *G* be a multigraph containing no minor isomorphic to *K*_{3,3} or *K*_{5}*e* (where *K*_{5}*e* denotes *K*_{5} without one ot its edges). We show that the chromatic index of *G* is given by , where *p* is the maximum valency of *G* and *k* is defined as (*w*(*E*(*S*)) being the number of edges in the subgraph induced by *S*). This result verifies a conjecture of Seymour [J. Combin. Theory (B) 31 (1981), pp. 82-94] and is actually a generalization of a result proven by Seymour [Combinatorica 10 (1990), pp. 379-392] for series-parallel graphs. It is also equivalent to the following statement: the matching polytope of a graph containing neither *K*_{5}*e* nor *K*_{3,3} as a minor has the integer decomposition property.

Published **January 1997**
,
36 pages

This cahier was revised in **August 2000**