特殊图b-色数的相关性质  

Some Properties on the b-chromatic Number of Special Graphs

作　　者：王国兴 曹晓军 WANG Guo-xing;CAO Xiao-jun(Gansu Silk Road Economic Research Institute,Lanzhou University of Finance and Economics,Lanzhou 730020;College of Information Engineering,Lanzhou University of Finance and Economics,Lanzhou 730020)

机构地区：[1]兰州财经大学丝绸之路经济研究院,兰州730020 [2]兰州财经大学信息工程学院,兰州730020

出　　处：《工程数学学报》2021年第2期293-300,共8页Chinese Journal of Engineering Mathematics

基　　金：国家自然科学基金(61662066;11761064);甘肃省高等学校创新能力提升项目(2019A-070);兰州财经大学丝绸之路经济研究院重点课题(JYYZ201703).

摘　　要：图染色是图论中研究热点问题之一,在许多领域都有重要的应用.用χ(G)和φ(G)分别表示连通图G的色数和b-色数.对连通图R,S,称图G不含导出{R,S},如果图G不含同构于R和S的导出子图.本文证明了对任意连通的至少4个顶点的图R,S,连通(或者2-边连通或者2-连通)不含{R,S}的图G满足χ(G)=φ(G)当且仅当{R,S}≼{P5,Z1}.其中P5是5个顶点的路,Z1是将P2和三角形的一个顶点粘合所得的图.此外,给出了特殊interlacing图IGn,2和IGn,3的b-色数的下界.Graph coloring is one of the most hot issues in graph theory and has important applications in many fields.For a connected graph G,we useχ(G)andφ(G)to denote the chromatic number and b-chromatic number of G,respectively.Let R,S be two connected graphs.Then G is said to be{R,S}-free if G does not contain R and S as induced subgraphs.In this paper,we prove that for any connected graphs R and S of order at least 4,every connected(2-edge-connected or 2-connected){R,S}-free graph G impliesχ(G)=φ(G)if and only if{R,S}≼{P5,Z1},where P5 is a path of order 5 and Z1 is the graph obtained by identifying one vertex of P2 and one vertex of a triangle.Besides,we give the lower bound of b-chromatic numbers of two special classes of interlacing graphs IGn,2 and IGn,3.

关 键 词：色数 b-色数 导出子图 interlacing图 

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