TransWikia.com

Uniquely 4-colorable Planar Graph Conjecture?

Theoretical Computer Science Asked on October 30, 2021

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?

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP