共查询到20条相似文献,搜索用时 963 毫秒
1.
关于距离图着色问题的一点结果 总被引:3,自引:0,他引:3
整数距离图是这样一类图G(Z,D),其中V(G)=Z,两点u,v之间有一条边相连,当且仅当|u-v|∈D,这里D∈ N.本文确定了|D|≥4时某些距离图G(Z,D)的点色数χ(G),解决了|D|=3时某些距离图G(Z,D)的star extremal问题. 相似文献
2.
段芳 《新疆师范大学学报(自然科学版)》2014,(1):78-80
Erodos证明了对于一个图G ,χ(G)-ω(G)可以任意大。因此,对一般图而言,其色数不一定能找到一个与团数有关的上界。文章主要研究了一类 F-free图的色数和团数的关系。得到了如果图G是一个不含K 1+ P3和C4作为导出子图的图,那么当α(G )≥3时,χ(G )=ω(G );当α(G )=2时,χ(G )n ≤2ω(G )。 相似文献
3.
大边数图的星约束色数 总被引:1,自引:0,他引:1
图的P-色数χ(G,P)是对G的顶点着色,使得每一色类的导出子图具有性质P的最小颜色数,该文研究χ(G,P),这里P是星的并这一性质,且把这种P-色数星约束色数,记为χ(G,St),该文给出一些大边数图的星约束色数。 相似文献
4.
5.
引入了最佳配点,最佳配邻点集的概念,讨论了3-色数的界,给出了x3(G)+x3(G^-)的可达下界。 相似文献
6.
7.
吴建良 《山东科技大学学报(自然科学版)》1996,(2)
设V(G)、E(G)和F(G)分别为平面图G的点集、边集和面集。G的完备色数Xc(G)是使得V(G)∪E(G)∪F(G)中相邻或相关联的元素间均染不同色的最少颜色数。本文证明了:对无割点的外平面图G,有Xc(G)≤max{7,△(G)+1},其中△(G)为G的最大度数。 相似文献
8.
Cayley色图的强连通性 总被引:3,自引:0,他引:3
简国明 《云南大学学报(自然科学版)》1997,19(5):456-459
应用群论方法,给出并证明了一般有限群的Cayley色图D(F,S)的强连通分支数为[F:(S)],以及强连通的Cayley色图D(F,S)的强连通度的下界为[|S|2]+1. 相似文献
9.
分式色数和,点、色数是图的两个重要参数.本文在文献[1]的基础上给出了两类距离图G(Z,Dm,k,k+1)与G(Z,Dm,kk+1,K+2)的分式色数和点色数. 相似文献
10.
图G的圆色数xc(G)(也称为星色数)是图的色数的一种推广,给出了图的圆色数等于其色数的一些充分条件。 相似文献
11.
12.
一类距离图的分数色数 总被引:1,自引:0,他引:1
摘要:主要讨论了距离图G(Z,Dm,k,k+1,k+2,k+3)(其中Dm,k,k+1,k+2,k+3={1,2,…,m}-{k,k+1,k+2,k+3})的分数色数,以及当2k≤m≤2k+5时G(Z,Dm,k,k+1,k+2,k+3)的色数。 相似文献
13.
14.
连广昌 《南京邮电大学学报(自然科学版)》1995,(2)
证明了图的逻辑积的色数公式x(G1∧G2∧…∧Gn)≤min{x(G1),x(G2),…,x(Gn)},边色数有并作如下猜想:x(G1∧G2∧…∧Gn)=min{x(G1),x(G2),…,x(Gn)}. 相似文献
15.
研究单圈Cn’,一类单圈图G以及它们与完全图Km联图Cn’∨Kn,G∨Kn的全染色问题.借助于已知的完全图全染色的相关引理以及归纳总结的方法得出了Cn’,G的全色数以及其与完全图联图Cn’∨Kn,G∨Kn的全色数,从而验证了对这类图全染色猜想的正确性. 相似文献
16.
臧运华 《东北师大学报(自然科学版)》1999,(3):20-23
利用图的色多项式和图的结构间的内在联系,以及图的色数和点的度之间的关系,把满足一定条件的图分成几种情形,证明了当n≥3,m≥3时,由完全图Kn和图Cm重叠于一条边得到的一类科是色唯一的。 相似文献
17.
王志坚 《苏州科技学院学报(自然科学版)》1994,(2)
分别以X(G)、X1(G)、X2(G)记图G之色数、边色数和全色数,对任意p阶简单图G及其补图G,本文得到以下Nordhaus-Gaddum型结论:本文还指出,上面所有下界、上界对每个正整数p均可达到。 相似文献
18.
主要研究外平面图的松驰竞赛色数。如果缺陷度d =2 ,3 ,4 ,k =7-d ,我们能够分别给Alice一个策略 ,使得对 (k ,d) 松弛染色竞赛Alice能赢。 相似文献
19.
田双亮 《西北民族学院学报》2005,26(2):1-3
通过研究若干n重积图的边色数及点可区别边色数,就可证明■(Gi)=△(Gi),i=1,2,L,n,则∑=′×××=■△(G_i)其中G1×G2×L×Gn为G1,G2,L,Gn的n重积图. 相似文献
20.
一些特殊平面图的圆色数 总被引:5,自引:0,他引:5
给出了四类无穷族平面图的圆色数:第一族平面图的圆色数介于3和4之间;最后两族平面图的圆色数都是7/2;第二族平面图的圆色数为11/3,这是一族满足圆色数介于7/2和4之间的无穷族平面图,回答了Gao提出的问题. 相似文献