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

On coloring of graphs of girth 2l+1 without longer odd holes

作　　者：吴狄 许宝刚[1] 许怡安 Di Wu;Baogang Xu;Yian Xu

机构地区：[1]南京师范大学数学科学学院,南京210023 [2]东南大学数学学院,南京211189

出　　处：《中国科学：数学》2023年第1期103-120,共18页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:11931006,12101117);江苏省自然科学基金(批准号:BK20200344)资助项目。

摘　　要：称一个图中长度至少为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-可染色图一定不包含θ^(+)为导出子图.A hole is an induced cycle of length at least 4.Let l≥2 be an integer and r=min{l-1,[l/2]+1},let G_(l)denote the family of graphs which have girth 2l+1 and have no holes of odd length at least 2l+3,and let G∈G_(l).For a vertex u∈V(G)and a nonempty set S■V(G),let d(u,S)=min{d(u,v):v∈S},and let Li(S)={u∈V(G)and d(u,S)=i}for any integer i≥0.We show that if G[S]is connected and G[Li(S)]is bipartite for each i∈{1,…,r},then G[Li(S)]is bipartite for each i>0,and consequentlyχ(G)≤4,where G[S]denotes the subgraph induced by S.Letθ^(-)be the graph obtained from the Petersen graph by deleting three vertices which induce a path,letθ^(+)be the graph obtained from the Petersen graph by deleting two adjacent vertices,and letθbe the graph obtained fromθ^(+)by removing an edge incident with two vertices of degree 3.For a non-Petersen graph G∈G_(2),we show that if G is 3-connected and has no unstable 3-cutset then G must induce eitherθorθ^(-)but does not induceθ^(+).As corollaries,χ(G)≤3 for every graph G of G_(2)that induces neitherθnorθ^(-),and minimal non-3-color able graphs of G_(2)induce noθ^(+).

关 键 词：围长 奇洞 色数 

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