共查询到20条相似文献,搜索用时 0 毫秒
1.
给出了平面图的一个结构性定理,并证明了每个没有5-圈,相邻三角形,相邻四边形的平面图是(3,1)*-可选色的. 相似文献
2.
设Fk*是满足以下条件的3-正则2-连通平面图G所组成的图类,在G中存在这样的圈C,使得G-E(C)产生k个不相交的树T1,…,Tk(|E(Ti)|≥3,i=1,…,k),且这些树是按C的指定方向C*依次粘在圈C上的.本文主要证明了如下结果:Fk*中的图都是Hamilton的. 相似文献
3.
如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果. 相似文献
4.
5.
6.
循环着色是普通着色的推广.本文中,我们研究了一类平面图-“花图”的循环着色问题,证明了由2r 1个长为2n 1的圈构成的“辐路”长度为m的花图Fr,m,n的循环色数是2 1/(n-m/2),并证明了在这类图中去掉任何一个点或边后,循环色数都严格减少但普通色数不减少,即这类图是循环色临界的但不是普通色临界的.同时,我们还研究了循环着色与图Gkd中的链之间的关系,给出了两个等价的条件. 相似文献
7.
8.
循环着色是普通着色的推广。本文中,我们研究了一类平面图的循环着色问题,并证明了这类平面图是循环色临界的,但不是普通色临界的,同时,我们还研究了循环着色与图G_k~d中的链之间的关系. 相似文献
9.
定义了一类极大外平面图:(r,k)--扇。证明了当G是以r个顶点的圈Qr为标定界环的(r,k)一扇,G'是以Qr为标定界环的任意极大外平面图时,G和G'有公共四染色;同时对△(G)=r-3的极大外平在图也得到相同的结论。从而证明了四色定理的等价命题在给定条件下成立。 相似文献
10.
Steinberg猜想既没有4-圈又没有5-圈的平面图是3色可染的. Xu, Borodin等人各自独立地证明了既没有相邻三角形又没有5-和7-圈的平面图是3 色可染的. 作为这一结果的推论, 没有4-, 5-和7-圈的平面图是3色可染的. 本文证明一个比此推论更接近Steinberg猜想的结果, 设G是一个既没有4-圈又没有5-圈的平面图, 若对每一个k∈{3, 6, 7}, G都不含(k, 7)-弦, 则G是3色可染的, 这里的(k, 7)-弦是指长度为7+k-2的圈的一条弦, 它的两个端点将圈分成两条路, 一条路的长度为6, 另一条路的长度为k-1. 相似文献
11.
12.
这篇注记证明判断一个图是否有3-正则子图的问题,即使对于节点次不超过4的平面力,仍然是NP-完全的,而且,此结果是最好的可能。 相似文献
14.
三正则平面图的对偶图的哈密顿性的注记 总被引:1,自引:0,他引:1
陈婵 《高校应用数学学报(A辑)》2001,16(2):248-250
本文给出了三正则平面图的对偶图为哈密顿图的一个充分条件。 相似文献
15.
图的色多项式P(G,x)是对图G用z(正整数)种颜色正常着色的数目。现在我们在实数或复数域上考虑图的色多项式P(G,x),并且Beraha&Kahane发现了具有复色根无限接近于4的平面图族。由此本文得到了一类平面图的色多项式和它的根. 相似文献
16.
图G的边分解是指将G分解成子图G1,G2,…,Gm,使得E(G)=E(G1)∪…∪E(Gm),且对任意i≠j有E(Gi)∩E(Gj)=?.若一个森林的每个连通分支都是路,则称该森林为线性森林.图G的线性荫度la(G)是指使得G可以边分解为m个线性森林的最小整数m.本文利用权转移方法证明了Δ(G)≥25的1-平面图G的线性荫度为[Δ(G)/2],这里Δ(G)是图G的最大度. 相似文献
17.
图G的星边染色是指G的一个正常边染色,使得G中任一长为4的路和长为4的圈均不是2-边染色的.图G的星边色数χ’st(G)表示图G有星边染色的最小颜色数.设G是最大度为Δ的平面图,我们证明了:(1)若G不含4-圈,则χ’st(G)≤[1.5Δ]+15;(2)若g≥5,则χ’st(G)≤[1.5Δ」+10;(3)若g=7,则χ’st(G)≤[1.5Δ」+6. 相似文献
18.
图G的一个无圈边着色是一个正常的边着色且不含双色的圈.图G的无圈边色数是图G的无圈边着色中所用色数的最小者.本文用反证法得到了不含5-圈的平面图G的无圈边色数的一个上界. 相似文献
19.
这篇注记证明判断一个图是否有3-正则子图的问题,即使对于节点次不超过4的平面图,仍然是NP-完全的。而且,此结果是最好的可能。 相似文献
20.
如果图G的一个正常边染色使得G中没有长为4的路或4-圈是2-边染色的,则称此染色是G的一个星边染色.对G进行星边染色所需的最少颜色数称为G的星边色数,记作x′s(G).该文证明了最大度为4的极大外平面图的星边色数等于6,对任一n(≥8)阶极大外平面图Gn,有6≤x′s(Gn)≤n-1成立,并且上界和下界都是可达的. 相似文献