含有3-圈的平面图的有效染色数  

The Valid Coloring Number of Plane Graphs Containing3-Cycles

作　　者：沈儒雄 

机构地区：[1]浙江师范大学数学科学学院,浙江 金华

出　　处：《应用数学进展》2025年第1期24-32,共9页Advances in Applied Mathematics

摘　　要：给定平面图G的一个顶点染色,如果图G的某个面F 的所有顶点颜色各不相同,我们称面F 为彩 虹面。 而如果平面图G中没有任何一个面是彩虹面,我们称这种染色为有效染色. 在这种有效 染色方案中,所使用的颜色种类的最大值定义为该平面图的有效染色数,记作χf (G)。 Jungiˇc, Kr´al/和Sˇkrekovski研究了一类围长至少为4的平面图的有效染色数。 本文主要研究了一类既包 含3-圈又包含长度至少为5的面圈的平面图的有效染色数井得到了它的下界。Given a vertex coloring of a plane graph G, if all the vertices of a face F of G receive mutually different colors, then the face F is called a rainbow face. A valid coloring is a coloring of G such that no face of G is rainbow. The maximum number of colors used in a valid coloring of a plane graph G is referred to as the valid coloring number, denoted by χf (G). Jungiˇc, Kr´al/ and Sˇkrekovski focused on the valid coloring number of a class of plane graphs with girth at least 4. In this paper, we mainly study the valid coloring number of a class of plane graphs containing 3-cycles and faces with cycles of length at least 5 and get its lower bound.

关 键 词：平面图 彩虹面 有效染色 

分 类 号：O15[理学—数学]