极大平面图的结构与着色理论(3)纯树着色与唯一4-色极大平面图猜想

doi:10.11999/JEIT160409

CORC > 北京大学 > 信息科学技术学院

	极大平面图的结构与着色理论(3)纯树着色与唯一4-色极大平面图猜想; Theory on Structure and Coloring of Maximal Planar Graphs (3) Purely Tree-colorable and Uniquely 4-colorable Maximal Planar Graph Conjectures
	许进
刊名	电子与信息学报
	2016
关键词	唯一4-色极大平面图猜想纯树着色猜想哑铃极大平面图递归极大平面图 Uniquely 4-colorable maximal planar graph conjecture Purely tree-colorable planar graph conjecture Dumbbell maximal planar graphs Recursive maximal planar graphs
DOI	10.11999/JEIT160409
英文摘要	一个极大平面图若是从4K 出发，不断地在三角面上嵌入3度顶点得到的，则称此极大平面图为递归极大平面图。唯一4-色极大平面图猜想是指：一个平面图是唯一4-可着色的当且仅当它是递归极大平面图。此猜想已有43年历史，是图着色理论中继四色猜想之后另一个著名的未解猜想。为此，该文相继深入研究了哑铃极大平面图与递归极大平面图的结构与特性，结合该系列文章(2)的扩缩运算，给出了证明唯一4-色极大平面图猜想的一种思路。; A maximal planar graph is called the recursive maximal planar graph if it can be obtained from 4 K 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 43 years of history, is a very influential conjecture in graph coloring theory after the Four-Color Conjecture. In this paper, 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 this series of article (2).; 国家973规划项目; 国家自然科学基金(61372191,61472012,61472433,61572046,61502012,61572492,61572153,61402437)基金项目国家973规划项目; 国家自然科学基金(61372191,61472012,61472433,61572046,61502012,61572492,61572153,61402437)Foundation Items:The National 973 Program of China; The National Natural Science Foundation of China; EI; 中文核心期刊要目总览(PKU); 中国科技核心期刊(ISTIC); 中国科学引文数据库(CSCD); 6; 1328-1339; 38
语种	中文
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/493828]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	许进. 极大平面图的结构与着色理论(3)纯树着色与唯一4-色极大平面图猜想, Theory on Structure and Coloring of Maximal Planar Graphs (3) Purely Tree-colorable and Uniquely 4-colorable Maximal Planar Graph Conjectures[J]. 电子与信息学报,2016.
APA	许进.(2016).极大平面图的结构与着色理论(3)纯树着色与唯一4-色极大平面图猜想.电子与信息学报.
MLA	许进."极大平面图的结构与着色理论(3)纯树着色与唯一4-色极大平面图猜想".电子与信息学报 (2016).