Structural theorem on plane graphs with application to the entire coloring number
Structural theorem on plane graphs with application to the entire coloring number
复制标题
DOI：
10.1002/(sici)1097-0118(199611)23:3
复制
发表时间：
1996-11
期刊：
影响因子：
--
通讯作者：
O. Borodin
中科院分区：
文献类型：
--
作者：
O. Borodin
1973年，克朗克（Kronk）和米切姆（Mitchem）（《离散数学》（5）255 - 260页）推测，每个平面图\(G\)的顶点、边和面可以用\(D(G)+4\)种颜色着色，其中\(D(G)\)是\(G\)的最大度，使得任何两个相邻或相关联的元素都被赋予不同的颜色。他们成功地对\(D(G)=3\)的情况验证了这一点。本文证明了一个关于平面图的结构定理，该定理意味着对于所有\(D(G)\geq7\)，这个猜想都是成立的。© 1996约翰威立父子公司
In 1973, Kronk and Mitchem (Discrete Math.(5) 255–260) conjectured that the vertices, edges and faces of each plane graph G may be colored with D(G) + 4 colors, where D(G) is the maximum degree of G, so that any two adjacent or incident elements receive distinct colors. They succeeded in verifying this for D(G) = 3. A structural theorem on plane graphs is proved in the present paper which implies the validity of this conjecture for all D(G) ≥ 7. © 1996 John Wiley & Sons, Inc.