On the Multigraph Overfull Conjecture

arXiv2302.13197MaRDI QIDQ6427657FDOQ6427657

Authors: Michael J. Plantholt, Songling Shan 

Publication date: 25 February 2023

Abstract: A subgraph $H$ of a multigraph $G$ is overfull if $|E(H)|>Delta(G)lfloor|V(H)|/2floor$. Analogous to the Overfull Conjecture proposed by Chetwynd and Hilton in 1986, Stiebitz et al. in 2012 formed the multigraph version of the conjecture as follows: Let $G$ be a multigraph with maximum multiplicity $r$ and maximum degree $Delta>frac13r|V(G)|$. Then $G$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph. In this paper, we prove the following three results toward the Multigraph Overfull Conjecture for sufficiently large and even $n$. (1) If $G$ is $k$-regular with $kger(n/2+18)$, then $G$ 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 $k$. (2) If $G$ contains an overfull subgraph and $delta(G)ger(n/2+18)$, then $ch{i}^{\prime }(G)=lceilchi{\text{'}}_f(G)ceil$, where $chi{\text{'}}_f(G)$ is the fractional chromatic index of $G$. (3) If the minimum degree of $G$ is at least $(1+varepsilon)rn/2$ for any $0<varepsilon<1$ and $G$ contains no overfull subgraph, then $ch{i}^{\prime }(G)=Delta(G)$. The proof is based on the decomposition of multigraphs into simple graphs and we prove a slightly weak version of a conjecture due to the first author and Tipnis from 1991 on decomposing a multigraph into constrained simple graphs. The result is of independent interests.

This page was built for publication: On the Multigraph Overfull Conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6427657)