2023/02/26 by Michael J. Plantholt, Songling Shan, Plantholt, Michael J. +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2302.13197
openalex publication_date 2023/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A subgraph H of a multigraph G is overfull if |E(H) | > Δ(G) \lfloor |V(H)|/2 \rfloor. 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 Δ>(1)/(3) r|V(G)|. Then G has chromatic index Δ(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 k≥ r(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 δ(G)≥ r(n/2+18), then χ'(G)=\lceil χ'f(G) \rceil, where χ'f(G) is the fractional chromatic index of G. (3) If the minimum degree of G is at least (1+ε)rn/2 for any 0<ε<1 and G contains no overfull subgraph, then χ'(G)=Δ(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.