Exact Edge-Colorings of Graphs without Prescribed Minors

摘要

Let =(V,E,w) be a multigraph, where V is the set of vertices of , E its set of edges, and w a vector of edge multiplicities. For a subset S of V, let w(E(S)) denote the number of edges whose ends belong to S. It is well known that the chromatic index of is greater than or equal to max(rho,k), where rho is the maximum valency of and k is defined as max(w(E(S))/(|S|/2)|S is a subset of V, |S| odd and |S|>1). ((r) denotes the largest integer not greater than r.) Seymour (8) has made the conjecture that the chromatic index of a planar multigraph is less than or equal to max (rho, (k), where (k) denotes -(-k). We give a general method for proving Seymour's conjecture when the multigraph contains a 2-vertex cutset and discuss the implications of this method for classes of graphs without prescribed minors.