Hilton's conjecture on subgraph-overfull graphs

About 3 years old · traced to

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)>∣V∣3\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.

References

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).

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.