Abstract: Let G₁,G₂,···,G_n be n graphs on the same vertex set V with |V|=n. If C is a cycle of length n such that each edge belongs to a different graph, then we call C a rainbow Hamilton cycle on {G₁,G₂,···,G_n}. Similarly, if P is a path of length n-1 such that each edge belongs to a different graph of G₁,G₂,···,G_n-1, then we call P a rainbow Hamilt on path on {G₁,G₂,···,G_n-1}. Recently, Joos and Kim have proved a rainbow version of Dirac theorem, i.e., if each of G₁,G₂,···,G_n has minimum degree at least n/2, then {G₁,G₂,···,G_n} contains a rainbow Hamilton cycle. In this paper, by the shifting method we show that if each of G₁,G₂,···,G_n has at least $\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+2$ edges, then {G₁,G₂,···,G_n} contains a rainbow Hamilton cycle. Moreover, if each of G₁,G₂,···,G_n-1 has at least $\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+1$ edges, then {G₁,G₂,···,G_n-1} contains a rainbow Hamilton path.
The shifting operator is a powerful tool in extremal set theory, which was invented by Erdös, Ko and Rado and further developed by Frankl. The shifting operator can be applied to graphs and hypergraphs and preserve the number of edges. It is well known that the shifting operator cannot increase the matching number of graphs and hypergraphs. In the present paper, we show that if a graph system {G₁,G₂,···,G_n} does not contain a rainbow Hamilton cycle, then one can apply the shifting operator to G₁,G₂,···,G_n simultaneously without producing a rainbow Hamilton cycle. By applying the shifting operator to G₁,G₂,···,G_n repeatedly, eventually we shall obtain a sequence of shifted graphs G₁,G₂,···,G_n.
For two pairs (x₁,x₂)and (y₁,y₂), define the shifted partial order＜as: (x₁,x₂)＜(y₁,y₂) if and only if either x₁≤y₁ and x₂≤y₂ or x₁≤y₂ and x₂≤y₁ hold. The shifted graphs have the following nice property: if x₁x₂ is an edge of G and G is shifted, then for any pair (x₁,x₂)＜(y₁,y₂),y₁y₂ is also an edge of G. Let H_n,a,b be a graph with the vertex set {1,2,···,n} such that (i)the subgraph induced by {1,2,···,a} is a complete graph; (ii){a+1,a+2,···,n} forms an independent set; (iii)The neighbors of x are 1,2,···,b for each x in{a+1,a+2,···,n}. It is easy to see that H_n,a,b is a shifted graph. Moreover, H_n,a,b is non-Hamiltonian if n-a≥b and a≥b.
By applying a technique developed by Akiyama and Frankl, we show that some G_i has to be a subgraph of H_n,a,b for some a and b. We prove the result by distinguishing two cases: n is odd and n is even. For n=2k, let f₁={1,2k},f₂={2,2k-1},···,f_k={k,k+1}and let f_k+1={2,2k},f_k+2={3,2k-1},···,f_2k-1={k,k+2},f_2k={1,k+1}. Then f₁,f₂,···,f_2k form a Hamilton cycle. Since {G₁,G₂,···,G_n} does not contain a rainbow Hamilton cycle, we infer that there exists i such that f_i$\notin$G_i. If i=2k, then {1,k+1}$\notin$E(G_n). By using the property of shifted graphs, we obtain that G_i has to be a subgraph of H_2k,k,0. If i≤k, then we have f_i={i,2k+1-i}$\notin$E(G_i). It follows that G_i has to be a subgraph of H_2k,2k-i,i-1. If i≥k, set j=i-k, then f_i={j,2k-j}$\notin$E(G_i). Since f_i＜f_j={j,2k+1-j},f_j$\notin$E(G_i). Then we can show that G_i has to be a subgraph of H_2k,2k-j,j-1.
For n=2k+1, let f₁={1,2k+1},f₂={2,2k},···,f_k={k,k+2}and let f_k+1={2,2k+1},f_k+2= {3,2k},···,f_2k={k+1,k+2},f_2k+1={1,k+1}. It is easy to see that these edges form a Hamilton cycle. Since {G₁,G₂,···,G_n}does not contain a rainbow Hamilton cycle, there exists i such that f_i$\notin$G_i. If i=2k+1,then {1,k+1}$\notin$E(G_i). Then G_i has to be a subgraph of H_2k+1,k,0. If i≥k+1, set j=i-k, then f_i={j+1,2k+2-j}$\notin$E(G_i), implying that G_i has to be a subgraph of H_{2k+1,2k+1-j,j}. If 1≤i≤k, then f_i={i,2k+2-i}$\notin$E(G_i). As f′={i+1,2k+2-i} satisfies f_i＜f′,G_i has to be a subgraph of H_{2k+1,2k+1-i,i}. By computations, we show that all these H_n,a,b graphs have at most $\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+1$ edges, which leads to a contradiction. Thus, we conclude that if each of G₁,G₂,···,G_n has at least $\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+2$ edges, then{G₁,G₂,···,G_n} contains a rainbow Hamiltonian cycle. By a similar argument, we establish the corresponding result for rainbow Hamiltonian paths as well.

Key words: Ore theorem, rainbow Hamiltonian cycle, rainbow Hamiltonian path

摘要： 设G₁,G₂,···,G_n是在同样的顶点集合V上的n个图,且满足|V|=n。设C是包含V中所有顶点的一个圈,如果C的边集合是从G₁,G₂,···,G_n中每个图选择一条边得到的,则称C为{G₁,G₂,···,G_n}上的一个彩色哈密尔顿圈。设P是包含V中所有顶点的一条路,如果P中每条边均来自G₁,G₂,···,G_n-1中不同的图,那么称P为{G₁,G₂,···,G_n-1}上的一个彩色哈密尔顿路。最近,Joos和Kim证明了彩色的Dirac定理, 即如果G₁,G₂,···,G_n中每个图的最小度都大于等于n/2,则{G₁,G₂,···,G_n}中包含一个彩色哈密尔顿圈。在本文中,我们采用移位方法证明了如果G₁,G₂,···,G_n中每个图的边数都大于等于$\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+2$,则{G₁,G₂,···,G_n}中包含一个彩色哈密尔顿圈。进一步地,如果G₁,G₂,···,G_n-1中每个图的边数都大于等于$\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+1$,则{G₁,G₂,···,G_n-1}中包含一条彩色哈密尔顿路。

关键词: Ore定理, 彩色哈密尔顿圈, 彩色哈密尔顿路