共查询到20条相似文献,搜索用时 15 毫秒
1.
完全3-部图K_(1,10,n)的交叉数 总被引:1,自引:0,他引:1
在上世纪五十年代初,Zarankiewicz猜想完全2-部图Km,m(m≤n)的交叉数为[m/2][m-1/2][n/2][n-1/2](对任意实数x,[x]表示不超过x的最大整数),目前只证明了当m ≤ 6时,Zarankiewicz猜想是正确的.假定Zarankiewicz猜想对m=11的情形成立,本文确定完全3-部图K1,10,n的交叉数. 相似文献
2.
《Discrete Mathematics》2019,342(4):1028-1037
For a given pair of two graphs , let be the smallest positive integer such that for any graph of order , either contains as a subgraph or the complement of contains as a subgraph. Baskoro, Broersma and Surahmat (2005) conjectured that for , where is the join of and . In this paper, we prove that this conjecture is true for the case . 相似文献
3.
Let brk(C4;Kn, n) be the smallest N such that if all edges of KN, N are colored by k + 1 colors, then there is a monochromatic C4 in one of the first k colors or a monochromatic Kn, n in the last color. It is shown that brk(C4;Kn, n) = Θ(n2/log2n) for k?3, and br2(C4;Kn, n)≥c(n n/log2n)2 for large n. The main part of the proof is an algorithm to bound the number of large Kn, n in quasi‐random graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 47‐54, 2011 相似文献
4.
Ingo Schiermeyer 《Journal of Graph Theory》2003,44(4):251-260
The cycle‐complete graph Ramsey number r(Cm, Kn) is the smallest integer N such that every graph G of order N contains a cycle Cm on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(Cm, Kn) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C3, K3) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n2 ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003 相似文献
5.
素数阶循环图和经典Ramsey数R(4,n)的三个新下界 总被引:1,自引:0,他引:1
研究了素数阶循环圈的基本性质,提出了寻求有效参数构造正则循环圈的新方法,得到了3个经典Ramsey数的新下界:R(4,17)≥164,R(4,18)≥182,R(4,22)≥282.这前2个结果填补了关于Ramsey数综述[2]的上下界表中的2个空白,第3个结果超过了目前已知的最好下界R(4,22)≥258, 相似文献
6.
关于二部图K(m,n)-2的色唯一性 总被引:7,自引:0,他引:7
设K(m,n)-2表示从完全二部图K(m,n)中删去任意2条边所得之图.本文证明了:1.若n≥m≥3,且n+m>((n-m)2+8)1/2+1/2(n-m)2+4,则K(m,n)-2是色唯一图;2.当m≥3时,K(m,m)-2,K(m,m+1)-2和K(m,m+2)-2均是色唯一图. 相似文献
7.
8.
设f是图G的一个正常全染色.对任意x∈V(G),令C(x)表示与点x相关联或相邻的元素的颜色以及点x的颜色所构成的集合.若对任意u,v∈V(G),u≠v,有C(u)≠C(v),则称.f是图G的一个点强可区别全染色,对一个图G进行点强可区别全染色所需的最少的颜色的数目称为G的点强可区别全色数,记为X_(vst)(G).讨论了完全二部图K_(1,n),K_(2,n)和L_(3,n)的点强可区别全色数,利用组合分析法,得到了当n≥3时,X_(vst)(K_(1,n)=n+1,当n≥4时,X_(vst)(K_(2,n)=n+2,当n≥5时,X_(vst)(K_(3,n))=n+2. 相似文献
9.
It is shown that the Ramsey number r(K2,s 1, K1,n) ≤ n √sn (s 3)/2 o(1) for large n, and r(K2,s 1, K1,n)∈{(q-1)2/s 1,-(q-1)2/s 2},wheren (q-1)2/s-q 2 and q is a prime power such that s|(q - 1). 相似文献
10.
The multicolor Ramsey number Rr(H) is defined to be the smallest integer n=n(r) with the property that any r-coloring of the edges of the complete graph Kn must result in a monochromatic subgraph of Kn isomorphic to H. It is well known that 2rm<Rr(C2m+1)<2(r+2)!m and Rr(C2m)≥(r−1)(m−1)+1. In this paper, we prove that Rr(C2m)≥2(r−1)(m−1)+2.
This research is supported by NSFC(60373096, 60573022) and SRFDP(20030141003) 相似文献
11.
本文研究完全三部图K(m,n,r)的色唯一性问题,通过比较两个色等价图的色划分数的方法,得出两个关于K(m,n,r)为色唯一图的一般形式数值条件,基本上解决了K(m,n,r)为色唯一图的判定问题. 相似文献
12.
通过比较两个图的色多项式的系数(本文使用了五独立集数)、顶点集、边集、三角形和四圈的个数,证明了K(2,2,6)是色唯一图,从而部分地回答了文[5],[7]中遗留的一个问题,并得到图K(n,n,n 4)(n=2或n 4)是色唯一的. 相似文献
13.
广义图K(n,m)的全色数 总被引:1,自引:0,他引:1
1965年,M.Behzad和Vizing分别提出了著名的全着色猜想:即对于简单图G有:XT(G)≤△+2,其中△是图G的最大度.本文确定了完全图Kn的广义图K(n,m)的全色数,并利用它证明了Lm×Kn(m≥3)是第Ⅰ型的. 相似文献
14.
Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article. 相似文献
15.
7个经典Ramsey数R(k,l)的新下界 总被引:11,自引:0,他引:11
利用构造性的方法,得到7个经典Ramsey数的新下界R(3,29)≥174,R(4,23)≥272,R(5,24)≥488,R(7,12)≥312,R(8,18)≥728,R(8,20)≥860,R(9,21)≥1278. 相似文献
16.
17.
Finding the smallest number of crosscaps that suffice to orientation-embed every edge signature of the complete bipartite graph is an open problem. In this paper that number for the complete bipartite graph , , is determined by using diamond products of signed graphs. The number is , which is attained by with exactly 1 negative edge, except that when , the number is 4, which is attained by with exactly 4 independent negative edges. 相似文献
18.
早在上世纪五十年代,Zarankiewicz猜想完全2-部图Km,n(m≤n)的交叉数为[m/2][m-1/2][n/2][n-1/2](对任意实数x,[x]表示不超过x的最大整数).目前这一猜想的正确只证明了当m≤6时成立.本文主要证明了若Zarankiewicz猜想对m=7成立,则完全3-部图K1,6,n的交叉数为9[n/2][n-1/2] 6[n/2]. 相似文献
19.
For given graphs , , the -color Ramsey number, denoted by , is the smallest integer such that if we arbitrarily color the edges of a complete graph of order with colors, then it always contains a monochromatic copy of colored with , for some . Let be a cycle of length and a star of order . In this paper, firstly we give a general upper bound of . In particular, for the 3-color case, we have and this bound is tight in some sense. Furthermore, we prove that for all and , and if is a prime power, then the equality holds. 相似文献
20.