共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
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 . 相似文献
3.
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. 相似文献
4.
《Discrete Mathematics》2020,343(12):112117
Let be an edge-colored graph of order . The minimum color degree of , denoted by , is the largest integer such that for every vertex , there are at least distinct colors on edges incident to . We say that an edge-colored graph is rainbow if all its edges have different colors. In this paper, we consider vertex-disjoint rainbow triangles in edge-colored graphs. Li (2013) showed that if , then contains a rainbow triangle and the lower bound is tight. Motivated by this result, we prove that if and , then contains two vertex-disjoint rainbow triangles. In particular, we conjecture that if , then contains vertex-disjoint rainbow triangles. For any integer , we show that if and , then contains vertex-disjoint rainbow triangles. Moreover, we provide sufficient conditions for the existence of edge-disjoint rainbow triangles. 相似文献
5.
6.
7.
《Discrete Mathematics》2022,345(12):113082
Let G be a graph of order n with an edge-coloring c, and let denote the minimum color-degree of G. A subgraph F of G is called rainbow if all edges of F have pairwise distinct colors. There have been a lot of results on rainbow cycles of edge-colored graphs. In this paper, we show that (i) if , then every vertex of G is contained in a rainbow triangle; (ii) if and , then every vertex of G is contained in a rainbow ; (iii) if G is complete, and , then G contains a rainbow cycle of length at least k, where . 相似文献
8.
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 δ. 相似文献
9.
10.
11.
A connected matching in a graph is a collection of edges that are pairwise disjoint but joined by another edge of the graph. Motivated by applications to Hadwiger’s conjecture, Plummer, Stiebitz, and Toft (2003) introduced connected matchings and proved that, given a positive integer , determining whether a graph has a connected matching of size at least is NP-complete. Cameron (2003) proved that this problem remains NP-complete on bipartite graphs, but can be solved in polynomial-time on chordal graphs. We present a polynomial-time algorithm that finds a maximum connected matching in a chordal bipartite graph. This includes a novel edge-without-vertex-elimination ordering of independent interest. We give several applications of the algorithm, including computing the Hadwiger number of a chordal bipartite graph, solving the unit-time bipartite margin-shop scheduling problem in the case in which the bipartite complement of the precedence graph is chordal bipartite, and determining–in a totally balanced binary matrix–the largest size of a square sub-matrix that is permutation equivalent to a matrix with all zero entries above the main diagonal. 相似文献
12.
《Discrete Mathematics》2019,342(7):1956-1965
13.
Dong Ye 《Discrete Mathematics》2018,341(5):1195-1198
It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph with has a maximum matching such that any two -unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for -regular graphs with . All counterexamples for -regular graphs given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all -regular simple graphs and also -regular multigraphs with . 相似文献
14.
A Roman domination function on a graph G=(V(G),E(G)) is a function f:V(G)→{0,1,2} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. The weight of a Roman dominating function is the value f(V(G))=∑u∈V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. Cockayne et al. [E. J. Cockayne et al. Roman domination in graphs, Discrete Mathematics 278 (2004) 11-22] showed that γ(G)≤γR(G)≤2γ(G) and defined a graph G to be Roman if γR(G)=2γ(G). In this article, the authors gave several classes of Roman graphs: P3k,P3k+2,C3k,C3k+2 for k≥1, Km,n for min{m,n}≠2, and any graph G with γ(G)=1; In this paper, we research on regular Roman graphs and prove that: (1) the circulant graphs and , n⁄≡1 (mod (2k+1)), (n≠2k) are Roman graphs, (2) the generalized Petersen graphs P(n,2k+1)( (mod 4) and ), P(n,1) (n⁄≡2 (mod 4)), P(n,3) ( (mod 4)) and P(11,3) are Roman graphs, and (3) the Cartesian product graphs are Roman graphs. 相似文献
15.
The Ryser Conjecture which states that there is a transversal of size in a Latin square of odd order is equivalent to finding a rainbow matching of size in a properly edge-colored using colors when is odd. Let be the minimum degree of a graph. Wang proposed a more general question to find a function such that every properly edge-colored graph of order contains a rainbow matching of size , which currently has the best bound of by Lo. Babu, Chandran and Vaidyanathan investigated Wang’s question under a stronger color condition. A strongly edge-colored graph is a properly edge-colored graph in which every monochromatic subgraph is an induced matching. Wang, Yan and Yu proved that every strongly edge-colored graph of order at least has a rainbow matching of size . In this note, we extend this result to graphs of order at least . 相似文献
16.
C. Picouleau 《Discrete Mathematics》2010,310(24):3646-3647
Mkrtchyan, Petrosyan, and Vardanyan made the following conjecture: Every graph G with Δ(G)−δ(G)≤1 has a maximum matching whose unsaturated vertices do not have a common neighbor. We disprove this conjecture. 相似文献
17.
We study the the following question in Random Graphs. We are given two disjoint sets L,R with |L| = n and |R| = m. We construct a random graph G by allowing each x∈L to choose d random neighbours in R. The question discussed is as to the size μ(G) of the largest matching in G. When considered in the context of Cuckoo Hashing, one key question is as to when is μ(G) = n whp? We answer this question exactly when d is at least three. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 相似文献
18.
Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs and , the -colored Gallai–Ramsey number is defined to be the minimum integer such that and for every , every rainbow -free coloring (using all colors) of the complete graph contains a monochromatic copy of . In this paper, we first provide some exact values and bounds of . Moreover, we define the -colored bipartite Gallai–Ramsey number as the minimum integer such that and for every , every rainbow -free coloring (using all colors) of the complete bipartite graph contains a monochromatic copy of . Furthermore, we describe the structures of complete bipartite graph with no rainbow and , respectively. Finally, we find the exact values of (), (where is a subgraph of ), and by using the structural results. 相似文献
19.
20.