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

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.

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

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.