共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
3.
The rainbow number for the graph in is defined to be the minimum integer such that any -edge-coloring of contains a rainbow . As one of the most important structures in graphs, the rainbow number of matchings has drawn much attention and has been extensively studied. Jendrol et al. initiated the rainbow number of matchings in planar graphs and they obtained bounds for the rainbow number of the matching in the plane triangulations, where the gap between the lower and upper bounds is . In this paper, we show that the rainbow number of the matching in maximal outerplanar graphs of order is . Using this technique, we show that the rainbow number of the matching in some subfamilies of plane triangulations of order is . The gaps between our lower and upper bounds are only . 相似文献
4.
5.
6.
In this note, we determine the maximum number of edges of a k-uniform hypergraph, k≥3, with a unique perfect matching. This settles a conjecture proposed by Snevily. 相似文献
7.
8.
P.E. Haxell 《Journal of Combinatorial Theory, Series A》2006,113(1):67-83
Let Cn denote the 3-uniform hypergraph loose cycle, that is the hypergraph with vertices v1,…,vn and edges v1v2v3, v3v4v5, v5v6v7,…,vn-1vnv1. We prove that every red-blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of Cn, where N is asymptotically equal to 5n/4. Moreover this result is (asymptotically) best possible. 相似文献
9.
Given a graph G and a subgraph H of G, let rb(G,H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G,H) is called the rainbow number of H with respect to G. Denote as mK2 a matching of size m and as Bn,k the set of all the k-regular bipartite graphs with bipartition (X,Y) such that X=Y=n and k≤n. Let k,m,n be given positive integers, where k≥3, m≥2 and n>3(m−1). We show that for every GBn,k, rb(G,mK2)=k(m−2)+2. We also determine the rainbow numbers of matchings in paths and cycles. 相似文献
10.
The anti-Ramsey number of Erdös, Simonovits and Sós from 1973 has become a classic invariant in Graph Theory. To extend this invariant to Matroid Theory, we use the heterochromatic number of a non-empty hypergraph . The heterochromatic number of is the smallest integer such that for every colouring of the vertices of with exactly colours, there is a totally multicoloured hyperedge of .Given a matroid , there are several hypergraphs over the ground set of we can consider, for example, , whose hyperedges are the circuits of , or , whose hyperedges are the bases of . We determine for general matroids and characterise the matroids with the property that equals the rank of the matroid. We also consider the case when the hyperedges are the Hamiltonian circuits of the matroid. Finally, we extend the known result about the anti-Ramsey number of 3-cycles in complete graphs to the heterochromatic number of 3-circuits in projective geometries over finite fields, and we propose a problem very similar to the famous problem on the anti-Ramsey number of the -cycles. 相似文献
11.
Given two graphs G and H, let f(G,H) denote the maximum number c for which there is a way to color the edges of G with c colors such that every subgraph H of G has at least two edges of the same color. Equivalently, any edge-coloring of G with at least rb(G,H)=f(G,H)+1 colors contains a rainbow copy of H, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number rb(G,H) is called the rainbow number ofHwith respect toG, and simply called the bipartite rainbow number ofH if G is the complete bipartite graph Km,n. Erd?s, Simonovits and Sós showed that rb(Kn,K3)=n. In 2004, Schiermeyer determined the rainbow numbers rb(Kn,Kk) for all n≥k≥4, and the rainbow numbers rb(Kn,kK2) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(Km,n,kK2) for all k≥1. 相似文献
12.
13.
14.
For a given graph H and a positive n, the rainbow number ofH, denoted by rb(n,H), is the minimum integer k so that in any edge-coloring of Kn with k colors there is a copy of H whose edges have distinct colors. In 2004, Schiermeyer determined rb(n,kK2) for all n≥3k+3. The case for smaller values of n (namely, ) remained generally open. In this paper we extend Schiermeyer’s result to all plausible n and hence determine the rainbow number of matchings. 相似文献
15.
16.
Ajit A. Diwan 《Discrete Mathematics》2019,342(4):1060-1062
Let be a perfect matching in a graph. A subset of is said to be a forcing set of , if is the only perfect matching in the graph that contains . The minimum size of a forcing set of is called the forcing number of . Pachter and Kim (1998) conjectured that the forcing number of every perfect matching in the -dimensional hypercube is , for all . This was revised by Riddle (2002), who conjectured that it is at least , and proved it for all even . We show that the revised conjecture holds for all . The proof is based on simple linear algebra. 相似文献
17.
Vojtech Rödl Andrzej Ruciński Endre Szemerédi 《Journal of Combinatorial Theory, Series A》2009,116(3):613-636
We define a perfect matching in a k-uniform hypergraph H on n vertices as a set of ⌊n/k⌋ disjoint edges. Let δk−1(H) be the largest integer d such that every (k−1)-element set of vertices of H belongs to at least d edges of H.In this paper we study the relation between δk−1(H) and the presence of a perfect matching in H for k?3. Let t(k,n) be the smallest integer t such that every k-uniform hypergraph on n vertices and with δk−1(H)?t contains a perfect matching.For large n divisible by k, we completely determine the values of t(k,n), which turn out to be very close to n/2−k. For example, if k is odd and n is large and even, then t(k,n)=n/2−k+2. In contrast, for n not divisible by k, we show that t(k,n)∼n/k.In the proofs we employ a newly developed “absorbing” technique, which has a potential to be applicable in a more general context of establishing existence of spanning subgraphs of graphs and hypergraphs. 相似文献
18.
19.
Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let δ denote the minimum degree of G. We show that if |V(G)| > (δ
2 + 14δ + 1)/4, then G has a rainbow matching of size δ, which answers a question asked by G. Wang [Electron. J. Combin., 2011, 18: #N162] affirmatively. In addition, we prove that
if G is a properly colored bipartite graph with bipartition (X, Y) and max{|X|, |Y|} > (δ
2 + 4δ − 4)/4, then G has a rainbow matching of size δ. 相似文献
20.