Hilton's conjecture on subgraph-overfull graphs

From papers

Let GG be a graph, let VV and EE denote its vertex and edge sets, and let Δ(G)\Delta(G) be its maximum degree. A graph is Class 1 if its edges can be properly colored with Δ(G)\Delta(G) colors; otherwise it is Class 2. A graph is subgraph-overfull if it has a subgraph HH satisfying V(H)|V(H)| odd and

E(H)>Δ(G)V(H)12.|E(H)|>\Delta(G)\frac{|V(H)|-1}{2}.

Hilton's conjecture. If Δ(G)>V3\Delta(G)>\frac{|V|}{3}, then GG is Class 1 if and only if it is not subgraph-overfull. The supplied paper states that this conjecture holds for the class of split graphs with stretch index σ=2\sigma=2, but does not establish its general status.

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

Fernanda Couto, Diego Amaro Ferraz and Sulamita Klein, “New Results on Edge-coloring and Total-coloring of Split Graphs”, arXiv:2303.05723 (2024).

Solutions 0

No solutions have been posted yet.