← All problems

Cao–Chen edge-decomposition conjecture

For every finite loopless multigraph GG with maximum degree Δ(G)\Delta(G) and edge-chromatic number χ′(G)=Δ(G)+k\chi'(G)=\Delta(G)+k, where k≥1k\ge 1, there exist spanning Class I subgraphs HΔH_\Delta and HkH_k such that E(G)E(G) is the disjoint union of E(HΔ)E(H_\Delta) and E(Hk)E(H_k), and Δ(HΔ)=Δ(G)\Delta(H_\Delta)=\Delta(G) and Δ(Hk)=k\Delta(H_k)=k.

References

Progress summary

Refreshed
Open · solution reported

A 2026 preprint claims the conjectured decomposition is proved for finite loopless multigraphs, but the claim has not been independently checked.

The tracked assertion concerns decomposing a finite loopless multigraph GG with edge-chromatic number χ′(G)=Δ(G)+k\chi'(G)=\Delta(G)+k into two class-I subgraphs of maximum degrees Δ(G)\Delta(G) and kk. The 2023 paper by Cao, Jing, Luo, Mkrtchyan, Zhang, and Zhao proves this formulation and identifies it as a variation of the Mkrtchyan–Steffen conjecture.

Known results

  • For k≥1k\ge 1, the cited 2023 paper states the decomposition into class-I subgraphs with maximum degrees Δ(G)\Delta(G) and kk; it also proves a broader decomposition with the second maximum degree at most the edge multiplicity.

October 15, 2026 reported proof

A preprint by Yonglei Chen and Yan Cao is reported as establishing the conjectured two-subgraph decomposition throughout the stated range. The retrieved evidence contains no independent assessment, and the source itself is unrefereed. The paper’s broader Conjecture 4.1, allowing arbitrary p,q≤Δ(G)p,q\le\Delta(G) with p+q=Δ(G)+kp+q=\Delta(G)+k, was not reported as proved.

Current status (as of October 2026): The stated two-subgraph formulation is claimed proved for finite loopless multigraphs, but that claim is supported only by an unrefereed preprint; the broader formulation remains open in the retrieved evidence.

Sources

Solutions 0

No solutions have been posted yet.