Problem dossier · Graph Decompositions
Overfull conjecture
A graph with maximum degree Δ > n/3 is class 2 (chromatic index Δ + 1) if and only if it contains an overfull subgraph — one with more edges than Δ·⌊|V|/2⌋.
§1
Status
Open. Known consequences would include the 1-factorization conjecture; verified in many special classes.
Think you can crack this one? Read the playbook before you announce →
§2
The Angle of Attack
Generate and classify small class-2 graphs with Δ > n/3, checking each for overfull subgraphs; automate the search for a counterexample candidate.
Tags: edge coloring · chromatic index · class 2 · overfull
§3
The Lab
No instruments built yet. When this problem gets tackled, its interactive instruments — explorers, searches, verifiers running in the browser — live here. See the Collatz dossier for what a fully tackled problem looks like.
§4
The Log
Empty. Work on this problem gets logged here as dated entries — constructions tried, code run, dead ends included. Dead ends are results.
§5
Related Problems
More open problems in Graph Decompositions and adjacent territory.
- 1-Factorization conjecture — Graph Decompositions
- Erdős–Sós conjecture — Graph Decompositions
- Gallai's path decomposition conjecture — Graph Decompositions
- Linear arboricity conjecture — Graph Decompositions