Figueiredo et al.'s conjecture on chordal graph edge-coloring

About 3 years old · traced to

Let GG be a chordal graph, meaning a graph with no induced cycle of length at least 44. Let Δ(G)\Delta(G) be its maximum degree. A graph is Class 2 if its edges cannot be properly colored with Δ(G)\Delta(G) colors, and it 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}.

Figueiredo et al.'s conjecture. GG is Class 2 if and only if it is subgraph-overfull. This conjecture proposes a characterization of edge-chromatic Class 2 chordal graphs by the subgraph-overfull obstruction. The supplied text gives no resolution beyond noting that the paper's results cover a class of split graphs.

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.