共查询到20条相似文献,搜索用时 218 毫秒
1.
In this paper we study three-color Ramsey numbers. Let K
i,j
denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G
1, G
2 and G
3, if r(G
1, G
2)≥s(G
3), then r(G
1, G
2, G
3)≥(r(G
1, G
2)−1)(χ(G
3)−1)+s(G
3), where s(G
3) is the chromatic surplus of G
3; (ii) (k+m−2)(n−1)+1≤r(K
1,k
, K
1,m
, K
n
)≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K
k,m
, K
k,m
, K
n
)≤c(n/logn), and r(C
2m
, C
2m
, K
n
)≤c(n/logn)
m/(m−1)
for sufficiently large n.
Received: July 25, 2000 Final version received: July 30, 2002
RID="*"
ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of
education ministry of China, and the foundations of Jiangsu Province
Acknowledgments. The authors are grateful to the referee for his valuable comments.
AMS 2000 MSC: 05C55 相似文献
2.
Carsten Schultz 《Journal of Combinatorial Theory, Series A》2011,118(8):2291-2318
The stable Kneser graph SGn,k, n?1, k?0, introduced by Schrijver (1978) [19], is a vertex critical graph with chromatic number k+2, its vertices are certain subsets of a set of cardinality m=2n+k. Björner and de Longueville (2003) [5] have shown that its box complex is homotopy equivalent to a sphere, Hom(K2,SGn,k)?Sk. The dihedral group D2m acts canonically on SGn,k, the group C2 with 2 elements acts on K2. We almost determine the (C2×D2m)-homotopy type of Hom(K2,SGn,k) and use this to prove the following results.The graphs SG2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG2s,4,H) is (r−1)-connected, the chromatic number χ(H) is at least r+6.If k∉{0,1,2,4,8} and n?N(k) then SGn,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SGn,k,G) is (r−1)-connected and χ(G)<r+k+2. 相似文献
3.
A tree is called a k-tree if the maximum degree is at most k. We prove the following theorem, by which a closure concept for spanning k-trees of n-connected graphs can be defined. Let k ≥ 2 and n ≥ 1 be integers, and let u and v be a pair of nonadjacent vertices of an n-connected graph G such that deg
G
(u) + deg
G
(v) ≥ |G| − 1 − (k − 2)n, where |G| denotes the order of G. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. 相似文献
4.
Jian Wang 《高校应用数学学报(英文版)》2008,23(3):345-350
A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that (1) m ≤ kn, (2) n ≤ km, (3) km-n = kn-m ≡ 0 (mod (k^2- 1)) and (4) λ(km-n)(kn-m) ≡ 0 (mod k(k- 1)(k^2 - 1)(m + n)). 相似文献
5.
Raphael Yuster 《Order》2003,20(2):121-133
Let TT
k
denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TT
k
by replacing each vertex with an independent set of size h≥1. The following result is proved: Let c
2=1/2, c
3=5/6 and c
k
=1−2−k−log k
for k≥4. For every ∈>0 there exists N=N(∈,h,k) such that for every undirected graph G with n>N vertices and with δ(G)≥c
k
n, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most ∈n vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k≥4, c
k
cannot be improved to less than 1−2−0.5k(1+o(1)).
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
6.
Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s
3(G) ≥ 2
k
−3, where s
r
(G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s
3(G) < 2
k
−2, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C
k
by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W
n
by deleting all but s consecutive spokes.
Received: January 29, 1999 Final version received: April 8, 2000 相似文献
7.
Dr. Matthias Kriesell 《Combinatorica》2006,26(3):277-314
A non-complete graph G is called an (n,k)-graph if it is n-connected but G—X is not (n−|X|+1)-connected for any X ⊂V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism).
Here we prove this conjecture. 相似文献
8.
We study some of the combinatorial structures related to the signature ofG-symmetric products of (open) surfacesSP
G
m
(M)=M
m/G whereG ⊂S
m.The attention is focused on the question, what information about a surfaceM can be recovered from a symmetric productSP
n(M). The problem is motivated in part by the study of locally Euclidean topological commutative (m+k,m)-groups, [16]. Emphasizing a combinatorial point of view we express the signature Sign(SP
G
m
(M))in terms of the cycle index
ofG, a polynomial which originally appeared in Pólya enumeration theory of graphs, trees, chemical structures etc. The computations
are used to show that there exist punctured Riemann surfacesM
g,k,M
g′,k′such that the manifoldsSP
m(M
g,k)andSP
m(M)g′,k′)are often not homeomorphic, although they always have the same homotopy type provided 2
g
+k=2
g′
+k′ andk,k′≥1.
Supported by the Serbian Ministry for Science and Technology, Grant No. 1643. 相似文献
9.
Hong Wang 《Graphs and Combinatorics》2001,17(1):177-183
Let G=(V
1,V
2;E) be a bipartite graph with 2k≤m=|V
1|≤|V
2|=n, where k is a positive integer. We show that if the number of edges of G is at least (2k−1)(n−1)+m, then G contains k vertex-disjoint cycles, unless e(G)=(2k−1)(n−1)+m and G belongs to a known class of graphs.
Received: December 9, 1998 Final version received: June 2, 1999 相似文献
10.
Recently, B. Y. Chen introduced a new intrinsic invariant of a manifold, and proved that everyn-dimensional submanifold of real space formsR
m
(ε) of constant sectional curvature ε satisfies a basic inequality δ(n
1,…,n
k
)≤c(n
1,…,n
k
)H
2+b(n
1,…,n
k
)ε, whereH is the mean curvature of the immersion, andc(n
1,…,n
k
) andb(n
1,…,n
k
) are constants depending only onn
1,…,n
k
,n andk. The immersion is calledideal if it satisfies the equality case of the above inequality identically for somek-tuple (n
1,…,n
k
). In this paper, we first prove that every ideal Einstein immersion satisfyingn≥n
1+…+n
k
+1 is totally geodesic, and that every ideal conformally flat immersion satisfyingn≥n
1+…+n
k
+2 andk≥2 is also totally geodesic. Secondly we completely classify all ideal semi-symmetric hypersurfaces in real space forms.
The author was supported by the NSFC and RFDP. 相似文献
11.
The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d
G
(x) + d
G
(y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d
G
(u) ≥ k. 相似文献
12.
For an ordered k-decomposition ? = {G
1, G
2,…,G
k
} of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(e|?) = (d(e, G
1), d(e, G
2),…,d(e, G
k
)), where d(e, G
i
) is the distance from e to G
i
. A decomposition ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K
n
) ≤⌊(2n + 5)/3⌋ for n≥ 3.
Received: June 17, 1998 Final version received: August 10, 1999 相似文献
13.
Hong Lin Xiao-feng Guo 《应用数学学报(英文版)》2007,23(1):155-160
Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!]. 相似文献
14.
Alexander Engström 《Discrete and Computational Geometry》2008,40(3):357-364
The Hom complexes were introduced by Lovász to study topological obstructions to graph colorings. The vertices of Hom(G,K
n
) are the n-colorings of the graph G, and a graph coloring is a partition of the vertex set into independent sets. Replacing the independence condition with any
hereditary condition defines a set partition complex. We show how coloring questions arising from, for example, Ramsey theory
can be formulated with set partition complexes.
It was conjectured by Babson and Kozlov, and proved by Čukić and Kozlov, that Hom(G,K
n
) is (n−d−2)-connected, where d is the maximal degree of a vertex of G. We generalize this to set partition complexes. 相似文献
15.
Some results on R
2-edge-connectivity of even regular graphs 总被引:1,自引:0,他引:1
XuJunming 《高校应用数学学报(英文版)》1999,14(3):366-370
Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an Rredge-cut if G-S is disconnected and comains neither an isolated vertex nor a one-degree vertex. The R2-edge-connectivity of G, denoted by λ^n(G), is the minimum cardinality over all R2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ^n(G)=g(2k-2) for any 2k-regular connected graph G (≠K5) that is either edge-transitive or vertex-transitive and g≥5 is given. 相似文献
16.
In this paper we study the homotopy type of Hom(Cm,Cn), where Ck is the cyclic graph with k vertices. We enumerate connected components of Hom(Cm,Cn) and show that each such component is either homeomorphic to a point or homotopy equivalent to S1. Moreover, we prove that Hom(Cm,Ln) is either empty or is homotopy equivalent to the union of two points, where Ln is an n-string, i.e., a tree with n vertices and no branching points. 相似文献
17.
Large Vertex-Disjoint Cycles in a Bipartite Graph 总被引:4,自引:0,他引:4
Hong Wang 《Graphs and Combinatorics》2000,16(3):359-366
Let s≥2 and k be two positive integers. Let G=(V
1,V
2;E) be a bipartite graph with |V
1|=|V
2|=n≥s
k and the minimum degree at least (s−1)k+1. When s=2 and n >2k, it is proved in [5] that G contains k vertex-disjoint cycles. In this paper, we show that if s≥3, then G contains k vertex-disjoint cycles of length at least 2s.
Received: March 2, 1998 Revised: October 26, 1998 相似文献
18.
Michael Ferrara 《Graphs and Combinatorics》2007,23(3):263-269
An integer sequence π is said to be graphic if it is the degree sequence of some simple graph G. In this case we say that G is a realization of π. Given a graph H, and a graphic sequence π we say that π is potentially H-graphic if there is some realization of π that contains H as a subgraph. We define σ(H,n) to be the minimum even integer such that every graphic sequence with sum at least σ(H,n) is potentially H-graphic. In this paper, we determine σ(H,n) for the graph H = Km1∪ Km2∪...∪ Kmk when n is a sufficiently large integer. This is accomplished by determining σ(Kj + kK2,n) where j and k are arbitrary positive integers, and considering the case where j = m − 2k and m = ∑ mi. 相似文献
19.
For a graph G, we define σ2(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ2(G) ≥ n + k − 1, then for any set of k independent vertices v
1,...,v
k
, G has k vertex-disjoint cycles C
1,..., C
k
of length at most four such that v
i
∈ V(C
i
) for all 1 ≤ i ≤ k. And show if σ2(G) ≥ n + k − 1, then for any set of k independent vertices v
1,...,v
k
, G has k vertex-disjoint cycles C
1,..., C
k
such that v
i
∈ V(C
i
) for all 1 ≤ i ≤ k, V(C
1) ∪...∪ V(C
k
) = V(G), and |C
i
| ≤ 4 for all 1 ≤ i ≤ k − 1.
The condition of degree sum σ2(G) ≥ n + k − 1 is sharp.
Received: December 20, 2006. Final version received: December 12, 2007. 相似文献
20.
Asymptotic Upper Bounds for Ramsey Functions 总被引:5,自引:0,他引:5
We show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nf
a
+1(d), where f
a
+1(d)=∫0
1(((1−t)1/(
a
+1))/(a+1+(d−a−1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(K
k
+
l
,K
n
)≤ (l+o(1))n
k
/(logn)
k
−1. In particular, r(K
k
, K
n
)≤(1+o(1))n
k
−1/(log n)
k
−2.
Received: May 11, 1998 Final version received: March 24, 1999 相似文献