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

From papers

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

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

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

Solutions 0

No solutions have been posted yet.