共查询到20条相似文献，搜索用时 15 毫秒
1.
Given two graphs G and H, let f(G,H) denote the minimum integer n such that in every coloring of the edges of Kn, there is either a copy of G with all edges having the same color or a copy of H with all edges having different colors. We show that f(G,H) is finite iff G is a star or H is acyclic. If S and T are trees with s and t edges, respectively, we show that 1+s(t?2)/2≤f(S,T)≤(s?1)(t2+3t). Using constructions from design theory, we establish the exact values, lying near (s?1)(t?1), for f(S,T) when S and T are certain paths or star‐like trees. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 1–16, 2003 相似文献
2.
Henry Liu Colton Magnant Akira Saito Ingo Schiermeyer Yongtang Shi 《Journal of Graph Theory》2020,94(2):192-205
3.
Motivated by questions in Ramsey theory, we consider colorings of the edges of the complete graph Kn that contain no rainbow path Pt+1 of length t. If fewer than t colors are used then certainly there is no rainbow Pt+1. We show that, if at least t colors are used, then very few colorings are possible if t ≤ 5 and these can be described precisely, whereas the situation for t ≥ 6 is qualitatively different. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 261–266, 2007 相似文献
4.
We study the local profiles of trees. We show that in contrast with the situation for general graphs, the limit set of k‐profiles of trees is convex. We initiate a study of the defining inequalities of this convex set. Many challenging problems remain open. 相似文献
5.
Consider the graph consisting of a triangle with a pendant edge. We describe the structure of rainbow ‐free edge colorings of a complete graph and provide some corresponding Gallai–Ramsey results. In particular, we extend a result of Gallai to find a partition of the vertices of a rainbow ‐free colored complete graph with a limited number of colors between the parts. We also extend some Gallai–Ramsey results of Chung and Graham, Faudree et al. and Gyárfás et al. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
6.
7.
8.
9.
10.
11.
We study colorings of the edges of the complete graph . For some graph , we say that a coloring contains a rainbow , if there is an embedding of into , such that all edges of the embedded copy have pairwise distinct colors. The main emphasis of this paper is a classification of those forbidden rainbow graphs that force a low number of vertices of a high color degree, along with some specifications and more general information in certain cases. Those graphs turn out to be of two special types of trees of small diameter. 相似文献
12.
超图H=(V,E)是一个二元组(V,E),其中超边集E中的元素是点集V的非空子集.因此图是一种特殊的超图,超图也可以看作是一般图的推广.特别地,如果超边集E中的元素均是点集V的k元子集,则称该超图为k-一致的.通常情况下,为叙述简便,我们也会将超边简称为边.图(超图)中的匹配是指图(超图)中互不相交的边的集合.对于图(超图)中的彩色匹配,有两种定义方式:一为染色图(超图)中互不相交且颜色不同的边的集合;二为顶点集均为[n]的多个染色图(超图)所构成的集族中互不相交且颜色均不同的边的集合,且每条边均来自集族中不同的图(超图).现主要介绍了图与超图中关于彩色匹配的相关结果. 相似文献
13.
Given a graph G and a positive integer k, define the Gallai–Ramsey number to be the minimum number of vertices n such that any k‐edge coloring of contains either a rainbow (all different colored) triangle or a monochromatic copy of G. In this work, we improve upon known upper bounds on the Gallai–Ramsey numbers for paths and cycles. All these upper bounds now have the best possible order of magnitude as functions of k. 相似文献
14.
Julia Böttcher Yoshiharu Kohayakawa Aldo Procacci 《Random Structures and Algorithms》2012,40(4):425-436
Let G be a graph on n vertices with maximum degree Δ. We use the Lovász local lemma to show the following two results about colourings χ of the edges of the complete graph Kn. If for each vertex v of Kn the colouring χ assigns each colour to at most (n ‐ 2)/(22.4Δ2) edges emanating from v, then there is a copy of G in Kn which is properly edge‐coloured by χ. This improves on a result of Alon, Jiang, Miller, and Pritikin [Random Struct. Algorithms 23(4), 409–433, 2003]. On the other hand, if χ assigns each colour to at most n/(51Δ2) edges of Kn, then there is a copy of G in Kn such that each edge of G receives a different colour from χ. This proves a conjecture of Frieze and Krivelevich [Electron. J. Comb. 15(1), R59, 2008]. Our proofs rely on a framework developed by Lu and Székely [Electron. J. Comb. 14(1), R63, 2007] for applying the local lemma to random injections. In order to improve the constants in our results we use a version of the local lemma due to Bissacot, Fernández, Procacci, and Scoppola [preprint, arXiv:0910.1824]. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 425–436, 2012 相似文献
15.
Let be a 1‐factorization of the complete uniform hypergraph with and . We show that there exists a 1‐factor of whose edges belong to n different 1‐factors in . Such a 1‐factor is called a “rainbow” 1‐factor or an “orthogonal” 1‐factor. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 487–490, 2007 相似文献
16.
We show the existence of rainbow perfect matchings in μn‐bounded edge colorings of Dirac bipartite graphs, for a sufficiently small μ > 0. As an application of our results, we obtain several results on the existence of rainbow k‐factors in Dirac graphs and rainbow spanning subgraphs of bounded maximum degree on graphs with large minimum degree. 相似文献
17.
Given a graph H and a positive integer n, Anti‐Ramsey number AR(n, H) is the maximum number of colors in an edge‐coloring of Kn that contains no polychromatic copy of H. The anti‐Ramsey numbers were introduced in the 1970s by Erd?s, Simonovits, and Sós, who among other things, determined this function for cliques. In general, few exact values of AR(n, H) are known. Let us call a graph H doubly edge‐critical if χ(H?e)≥p+ 1 for each edge e∈E(H) and there exist two edges e1, e2 of H for which χ(H?e1?e2)=p. Here, we obtain the exact value of AR(n, H) for any doubly edge‐critical H when n?n0(H) is sufficiently large. A main ingredient of our proof is the stability theorem of Erd?s and Simonovits for the Turán problem. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 210–218, 2009 相似文献
18.
The size Ramsey number of two graphs and is the smallest integer such that there exists a graph on edges with the property that every red-blue colouring of the edges of yields a red copy of or a blue copy of . In 1981, Erdős observed that and he conjectured that this upper bound on is sharp. In 1983, Faudree and Sheehan extended this conjecture as follows: They proved the case . In 2001, Pikhurko showed that this conjecture is not true for and , by disproving the mentioned conjecture of Erdős. Here, we prove Faudree and Sheehan's conjecture for a given and . 相似文献
19.
Jacob Fox 《Journal of Graph Theory》2008,57(2):89-98
The Ramsey multiplicity M(G;n) of a graph G is the minimum number of monochromatic copies of G over all 2‐colorings of the edges of the complete graph Kn. For a graph G with a automorphisms, ν vertices, and E edges, it is natural to define the Ramsey multiplicity constant C(G) to be , which is the limit of the fraction of the total number of copies of G which must be monochromatic in a 2‐coloring of the edges of Kn. In 1980, Burr and Rosta showed that 0 ≥ C(G) ≤ 21?E for all graphs G, and conjectured that this upper bound is tight. Counterexamples of Burr and Rosta's conjecture were first found by Sidorenko and Thomason independently. Later, Clark proved that there are graphs G with E edges and 2E?1C(G) arbitrarily small. We prove that for each positive integer E, there is a graph G with E edges and C(G) ≤ E?E/2 + o(E). © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 89–98, 2008 相似文献
20.