The Chromatic Number of(P_(5),HVN)-free Graphs

Let G be a graph.We useχ(G)andω(G)to denote the chromatic number and clique number of G respectively.A P_(5)is a path on 5 vertices,and an HVN is a K_(4)together with one more vertex which is adjacent to exactly two vertices of K_(4).Combining with some known result,in this paper we show that if G is(P_(5),HVN)-free,thenχ(G)≤max{min{16,ω(G)+3},ω(G)+1}.This upper bound is almost sharp.

围长2l+1且无长奇洞图的染色问题

称一个图中长度至少为4的导出圈为该图的洞,长度为奇数和偶数的洞分别被称为奇洞和偶洞.由Petersen图去掉一条2长路的顶点所得到的图记为θ^(-),由Petersen图去掉一对相邻顶点所得到的图记为θ^(+),由θ^(+)去掉一条关联两个3度顶点的边所得到的图记为θ.设l≥2为整数且令r=min{l-1,[l/2]+1},G_(l)表示围长为2l+1且不含其他长度奇洞的图类,G∈G_(l),u∈V(G),S■V(G)是一个非空子集.用G[S]表示由S导出的子图,定义d(u,S)=min{d(u,v):v∈S},并定义Li(S)={u∈V(G)且d(u,S)=i}.本文证明了,如果G[S]连通且对于每一个整数i∈{1,…,r}而言G[Li(S)]都是二部图,则对于所有整数i>0,G[Li(S)]都是二部图,从而χ(G)≤4.本文还证明了,若非Petersen图G∈G_(2)3-连通且所有3-顶点割集都是独立集,则G有导出子图θ或者θ^(-)但没有导出子图θ^(+).作为其推论,若图G∈G_(2)的导出子图中既没有θ又没有θ^(-),则χ(G)≤3,并且G_(2)中极小非3-可染色图一定不包含θ^(+)为导出子图.