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

Some Properties on the b-chromatic Number of Special Graphs

图染色是图论中研究热点问题之一,在许多领域都有重要的应用.用χ(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.