ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a simple graph. Write Δ(G)\Delta(G) for its maximum degree, and call GG overfull if

∣E(G)∣>Δ(G)⌊∣V(G)∣2⌋.|E(G)|>\Delta(G)\left\lfloor\frac{|V(G)|}{2}\right\rfloor.

A graph is of Class 2 when its chromatic index satisfies χ′(G)=Δ(G)+1\chi'(G)=\Delta(G)+1.

Overfull Conjecture. Let GG be a graph of Class 22 with

Δ(G)>∣V(G)∣3.\Delta(G)>\frac{|V(G)|}{3}.

Then GG contains an overfull subgraph HH with Δ(H)=Δ(G)\Delta(H)=\Delta(G).

This conjecture of Chetwynd and Hilton would make determining the chromatic index polynomial-time solvable for graphs with maximum degree greater than one third their order. It is known in several dense cases, including when Δ(G)≥∣V(G)∣−3\Delta(G)\geq |V(G)|-3 and for sufficiently large graphs with Δ(G)≥(1−ε)∣V(G)∣\Delta(G)\geq(1-\varepsilon)|V(G)| for 0<ε≤1/140<\varepsilon\leq 1/14, but remains open in general.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.