Group for Research in Decision Analysis


Optimal Edge-Colourings for a Class of Planar Multigraphs

Let G be a multigraph containing no minor isomorphic to K3,3 or K5e (where K5e denotes K5 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 K5e nor K3,3 as a minor has the integer decomposition property.

, 36 pages

This cahier was revised in August 2000