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)).

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Purely Tree-Colorable and Uniquely 4-Colorable Maximal Planar Graph Conjectures

  • Jin Xu

摘要

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)).