Mohar's conjecture on edge-critical graphs and strong chromatic-choosability

At least 7 years old · documented by

Let GG be a graph with maximum degree Δ(G)\Delta(G). It is (Δ(G)+1)(\Delta(G)+1)-edge-critical if it is (Δ(G)+1)(\Delta(G)+1)-edge-colorable, while every proper subgraph obtained by deleting at least one edge is Δ(G)\Delta(G)-edge-colorable. Let L(G)L(G) be the line graph of GG. A graph is strong kk-chromatic-choosable when it has chromatic number greater than k−1k-1 and satisfies the corresponding strong list-coloring condition described in the source.

Mohar's conjecture. If GG is a (Δ(G)+1)(\Delta(G)+1)-edge-critical graph, then L(G)L(G) is strong (Δ(G)+1)(\Delta(G)+1)-chromatic-choosable.

The conjecture was made by Mohar in 2001 and is presented in the source as an unresolved conjecture. The definition of strong chromatic-choosability is specialized, so its precise list-coloring formulation should be checked against the paper.

References

Primary source

Hemanshu Kaul and Jeffrey A. Mudrock, “Criticality, The List Color Function, and List Coloring the Cartesian Product of Graphs”, arXiv:1805.02147 (2018).

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.