特殊图b-色数的相关性质（英文）

作者：王国兴; 曹晓军

来源：工程数学学报, 2021, 38(02): 293-300.

• 色数
• b-色数
• 导出子图
• interlacing图

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

• 单位
  兰州财经大学