Multigraph Overfull Conjecture

About 3 years old · traced to

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.