子立方平面图的圈染色  

On the Cyclic Coloring of Subcubic Plane Graphs

作　　者：杨燕平 王维凡 邵慰慈[3] 陈敏 YANG Yanping;WANG Weifan;SHIU Wai Chee;CHEN Min(School of Basic Courses,Ningbo University of Finance and Economics,Ningbo,Zhejiang,315175,P.R.China;College of Mathematics and Computer Science,Zhejiang Normal University,Jinhua,Zhejiang,321004,P.R.China;Department of Mathematics,Hong Kong Baptist University,Kowloon Tong,Hongkong,999077,P.R.China)

机构地区：[1]宁波财经学院基础学院,宁波浙江315175 [2]浙江师范大学数学与计算机科学学院,金华浙江321004 [3]香港浸会大学数学系,九龙塘香港999077

出　　处：《数学进展》2022年第5期807-816,共10页Advances in Mathematics（China）

基　　金：Supported by NSFC(Nos.11771402,11471293)。

摘　　要：图G的圈染色是指G有一个正常的点染色,且G中同一个面上的顶点需要染不同的颜色.一个平面图G是圈k-可染的指的是G有一个圈k-染色.圈色数用符号χ_(c)(G)表示,是G圈k-可染的最小正整数k的值.图的圈染色猜想是指:任何一个平面图G的圈色数χ_(c)(G)≤[3/2Δ^(*)],其中Δ^(*)表示G的最大面度.到目前为止,当Δ^(*)=3,4,6时,猜想已经被证明.本文证明了若图G是一个Δ^(*)=5的子立方图,则猜想是成立的.进一步,得到了χ_(c)(G)=7的图例有且仅有三个.The cyclic chromatic numberχ_(c)(G)of a plane graph G is the smallest integer k for which G admits a proper vertex coloring using k colors such that any two vertices incident with the same face receive distinct colors.The Cyclic Coloring Conjecture asserts that every plane graph G with maximum face degreeΔ^(*)satisfiesχ_(c)(G)<[3/2Δ^(*)].This conjecture has been confirmed for plane graphs withΔ^(*)=3,4,6.In this paper,we show that every plane subcubic graph G with△^(*)=5 hasχ_(c)(G)≤7,and moreoverχ_(c)(G)=7 if and only if G is one of three specific graphs.

关 键 词：平面图 子立方图 圈色数 圈染色猜想 

分 类 号：O157.5[理学—数学]