My question is on Uniquely 4-colorable Planar Graph Conjecture mentioned in On purely tree-colorable planar graphs (and other papers of same(?) team such as "Theory on Structure and Coloring of Maximal Planar Graphs", etc.).

I find this paper a bit misleading.

  1. Uniquely 4-colorable Planar Graph "Conjecture"
    (in their paper, this is called "uniquely 4-colorable graph conjecture: vertex version")

To my knowledge, Fowler's characterization closed the case: he proved that a planar graph is uniquely 4-colourable iff it is a maximal planar chordal graph (also called planar 3-trees or Apollonian network). In the paper above, they give this as a conjecture(they call maximal planar chordal graphs as recursive maximal planar graphs) and cite Fisk. But, I do not see this conjecture in Fisk.

  1. They state that according to Fisk another known conjecture (If G is a uniquely 3-edge-colorable cubic graph, then G is a planar graph that contains a triangle) is equivalent to Uniquely 4-colorable Maximal Planar Graph Conjecture.

I don't think they are equivalent (or at least the equivalence is not obvious). The conjecture that uniquely 3-edge colourable graphs contain a triangle is still open. The other as we saw is closed.

Is there something I am missing?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.