Multigraph Overfull Conjecture

From papers

Let GG be a multigraph with no loops, and let μ(G)\mu(G) be its maximum edge multiplicity. Let Δ(G)\Delta(G) be its maximum degree, let χ(G)\chi'(G) be its chromatic index, and call a subgraph HH Δ(G)\Delta(G)-overfull when Δ(H)=Δ(G)\Delta(H)=\Delta(G) and E(H)>Δ(H)V(H)/2|E(H)|>\Delta(H)\lfloor |V(H)|/2\rfloor.

Multigraph Overfull Conjecture. If

Δ(G)>13μ(G)V(G),\Delta(G)>\frac{1}{3}\mu(G)|V(G)|,

then χ(G)=Δ(G)\chi'(G)=\Delta(G) if and only if GG contains no Δ(G)\Delta(G)-overfull subgraph.

This is the multigraph analogue of the Overfull Conjecture. The degree condition is shown in the source to be best possible using suitable multigraphs derived from the Petersen graph, but the conjecture itself is not resolved there.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Michael J. Plantholt and Songling Shan, “On the Multigraph Overfull Conjecture”, arXiv:2302.13197 (2023).

Solutions 0

No solutions have been posted yet.