Vertex-disjoint rainbow triangles in edge-colored graphs

Let $G$ be an edge-colored graph of order $n$. The minimum color degree of $G$, denoted by ${\delta }^c\left(G\right)$, is the largest integer $k$ such that for every vertex $v$, there are at least $k$ distinct colors on edges incident to $v$. 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 ${\delta }^c\left(G\right)\ge (n+1)∕2$, then $G$ contains a rainbow triangle and the lower bound is tight. Motivated by this result, we prove that if $n\ge 20$ and ${\delta }^c\left(G\right)\ge (n+2)∕2$, then $G$ contains two vertex-disjoint rainbow triangles. In particular, we conjecture that if ${\delta }^c\left(G\right)\ge (n+k)∕2$, then $G$ contains $k$ vertex-disjoint rainbow triangles. For any integer $k\ge 2$, we show that if $n\ge 16k-12$ and ${\delta }^c\left(G\right)\ge n∕2+k-1$, then $G$ contains $k$ vertex-disjoint rainbow triangles. Moreover, we provide sufficient conditions for the existence of $k$ edge-disjoint rainbow triangles.     

A Necessary and Sufficient Condition for the Existence of a Heterochromatic Spanning Tree in a Graph

We prove the following theorem. An edge-colored (not necessary to be proper) connected graph G of order n has a heterochromatic spanning tree if and only if for any r colors (1≤r≤n−2), the removal of all the edges colored with these r colors from G results in a graph having at most r+1 components, where a heterochromatic spanning tree is a spanning tree whose edges have distinct colors.     

A Ramsey‐type result for the hypercube

We prove that for every fixed k and ? ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Q_n with k colors contains a monochromatic cycle of length 2 ?. This answers an open question of Chung. Our techniques provide also a characterization of all subgraphs H of the hypercube which are Ramsey, that is, have the property that for every k, any k‐edge coloring of a sufficiently large Q_n contains a monochromatic copy of H. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 196–208, 2006     

关于Ramsey数下界的部分结果

本文得到 Ramsey数下界的一个计算公式 :R( l,s+ t-2 )≥ R( l,s) + R( l,t) -1 ,(式中 l、s、t≥ 3) .用此公式算得的 Ramsey数的下界比用其它公式算得的下界好 .     

Linear Ramsey numbers of sparse graphs

The Ramsey number R(G₁,G₂) of two graphs G₁ and G₂ is the least integer p so that either a graph G of order p contains a copy of G₁ or its complement G^c contains a copy of G₂. In 1973, Burr and Erd?s offered a total of $25 for settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory     

代数构造及在Ramsey理论中的应用

这篇文章在伽罗瓦域上的代数构造和关于一些特定类型图的Ramsey数之间建立了一个关系. 研究了关于伽罗瓦域上的代数构造的方程及方程组的解. 我们得到了一些关于二部图的Ramsey数的新的下界和上界.     

On Ramsey numbers of uniform hypergraphs with given maximum degree

For every ?>0 and every positive integers Δ and r, there exists C=C(?,Δ,r) such that the Ramsey number, R(H,H) of any r-uniform hypergraph H with maximum degree at most Δ is at most C|V(H)|^1+?.