Optimal Edge-Colourings for a Class of Planar Multigraphs

  Let G be a multigraph containing no minor isomorphic to or (where denotes without one of its edges). We show that the chromatic index of G is given by , where is the maximum valency of G and is defined as (w(E(S)) being the number of edges in the subgraph induced by S). This result partially 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 nor as a minor has the integer decomposition property. Received January 10, 1997/Revised September 13, 1999 The author is also affiliated with GERAD (école des Hautes études Commerciales de Montréal). Her work was supported by Grant OGP 0009126 from the Natural Sciences and Engineering Research Council of Canada (NSERC).