Purely Tree-Colorable and Uniquely 4-Colorable Maximal Planar Graph Conjectures
摘要
A maximal planar graph is called the recursive maximal planar graph if it can be obtained from \({K_4}\) by embedding a 3-degree vertex in some triangular face continuously. The uniquely 4-colorable maximal planar graph conjecture states that a planar graph is uniquely 4-colorable if and only if it is a recursive maximal planar graph. This conjecture, which has 46 years of history, is a very influential conjecture in graph coloring theory after the Four-Color Conjecture. In this chapter, the structures and properties of dumbbell maximal planar graphs and recursive maximal planar graphs are studied, and an idea of proving the uniquely 4-colorable maximal planar graph conjecture is proposed based on the extending-contracting operation proposed in Chap. 6 (Xu, J. Electron. Inf. Technol. 38(6), 1328–1353 (2016)).