不含{M(p,q),C_3,C_4}作为导出子图的图的色数

Authors：王晓; 汪小黎

Source：计算机与数字工程, 2015, (07): 1325-1327.

• 色数
• 导出子图
• 限制子图 chromatic number
• induced subgraph
• forbidden subgraph

Gyárfás曾猜想,设F是一个森林,对于每一个F-free的图G,存在整数函数f(F,ω(G))使得χ(G)f(F,ω(G))。利用一个引理,得到了每一个不含{M(p,q),C3,C4}作为导出子图的图是(p+q-1)-可着色的。

• Institution
  商洛学院