圈的推广Mycielski图的圆色数(英文)

Mycielski图是1955年由Mycielski提出来的．任给一个图G和一个非负整数m,G的推广Mycielski图μm(G)是G的Mycielski图的一个自然的推广．推广Mycielski图的性质以及它们的点色数、圆色数和分数色数等已有许多研究．本文研究圈的推广Mycielski图的圆色数．定义Cn为n个顶点的圈．对任意非负整数m和大于2的整数n,本文确定了图μm(Cn)的圆色数,同时还得到了图μm(Cn)-v的圆色数的一些结果．

广义Petersen图的弱点传递性

图X称为弱点传递图如果X的自同态幺半群EndX在顶点集V(X)上的作用是传递的 .本文给出了广义Petersen图是二分图的充要条件 ,刻划了奇围长小于 9的广义Petersen图的弱点传递性 ,作为推论给出了所有h ≤ 1 5的弱点传递的广义Pe tersen图P(h ,t) .

奇围长为s的本原无向图

本文证明了一类ｎ阶本原无向图有指数ｓ－１的一个充分必要条件。

奇围长(2t+1)的最小正则图

本文研究了奇围长(2~t+1) 的k-正则图的最少顶点数和极图。

具有围长对(g,h)的3—正则图

一个具有围长对(g,h)的k—正则图称为(k;g,h)一图,这种图的最小可能顶点数记作f(k;g,h). 本文证明了:f(3;5,8)=18,f(3;6,7)=18,f(3;7,8)=24,2/3(7S+4)≤f(3;6,2S+l)≤6S+4,k≥3;部分地回答了F·Harary在文[1]中提出的问题.

平面图的k-重(2k+2)-染色(英文)

G=(V,E)表示一个顶点集为V,边集为E的有限简单无向图.若存在映射Φ:V(G)→Z_k(n)(Z_k(n)是由{1,2,…,n}的所有k-元子集构成的集合),满足:(?)uv∈E(G),有Φ(u)∩(?)(v)=(?),则称Φ是G的一个k-重n-顶点染色.本文证明了奇围长至少为5k-7(k=4)或5k-9(k=6)的平面图G是k-重(2k+2)-可染的.

围长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-可染色图一定不包含θ^(+)为导出子图.

具有大的奇围长的符号图的圆环染色

图G的一个圆环r-染色(r≥2)是将G的每个顶点v对应到一个周长为r的圆上的点的一个映射f,使得对于G中任意的边xy,f(x)和f(y)在圆上的距离不小于1.G的圆环色数χc(G)是G存在圆环r-染色的最小实数r.符号图的圆环染色和图的圆环染色基本相同,不同的是对于负边xy,我们要求f(x)和f(y)的对点在圆上的距离不小于1.符号图(G,σ)的圆环色数是使得(G,σ)在圆环r-染色的最小实数r.本文证明:对于任意正整数k和实数ε>0,存在整数g使得对于任意树宽至多为k的符号图(G,σ),如果(G,-σ)的负围长至少是g,那么(G,σ)的圆环染色数至多是2+ε.