On the Multigraph Overfull Conjecture

ABSTRACT A subgraph of a multigraph is overfull if Analogous to the Overfull Conjecture proposed by Chetwynd and Hilton in 1986, Stiebitz et al. formed the multigraph version of the conjecture as follows: Let be a multigraph with maximum multiplicity and maximum degree . Then has chromatic index if and only if contains no overfull subgraph. In this paper, we prove the following three results toward the Multigraph Overfull Conjecture for sufficiently large and even , where . (1) If is ‐regular with , then has a 1‐factorization. This result also settles a conjecture of the first author and Tipnis from 2001 up to a constant error in the lower bound of . (2) If contains an overfull subgraph and , then , where is the fractional chromatic index of . (3) If the minimum degree of is at least for any and contains no overfull subgraph, then . The proof is based on the decomposition of multigraphs into simple graphs and we prove a slightly weaker version of a conjecture due to the first author and Tipnis from 1991 on decomposing a multigraph into constrained simple graphs. The result is also of independent interest.