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.
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.
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?
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP