Fabrici et al.'s four-color conjecture for facial unique-maximum edge-coloring

Let GG be a plane graph. Two distinct edges are facially adjacent if they are consecutive in some facial path, and a facial edge-coloring assigns distinct colors to facially adjacent edges. A FUM-edge-coloring is a facial edge-coloring in which each face is incident with a unique edge colored with the maximal color on that face. Write χfum(G)\chi_{\mathrm{fum}}'(G) for the minimum number of colors in such a coloring.

Fabrici et al.'s conjecture. If GG is a 22-edge-connected plane graph, then

χfum(G)4.\chi_{\mathrm{fum}}'(G) \leq 4.

The conjecture concerns the edge analogue of facial unique-maximum vertex-coloring. The paper proves the bound for 22-connected plane graphs, but does not resolve the stated 22-edge-connected version in full.

Sources & referencesView supporting material

Primary source

Vesna Andova, Bernard Lidický, Borut Lužar and Riste Škrekovski, “On facial unique-maximum (edge-)coloring”, arXiv:1708.00094 (2017).

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.