彩色Ore定理

A Rainbow Version of Ore Theorem

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

Let G_(1),G_(2),…,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_(1),G_(2),…,G_(n)}.Similarly,if P is a path of length n-1 such that each edge belongs to a different graph of G_(1),G_(2),…,G_(n-1),then we call P a rainbow Hamilt on path on{G_(1),G_(2),…,G_(n-1)}.Recently,Joos and Kim have proved a rainbow version of Dirac theorem,i.e.,if each of G_(1),G_(2),…,G_(n) has minimum degree at least n/2,then{G_(1),G_(2),…,G_(n)}contains a rainbow Hamilton cycle.In this paper,by the shifting method we show that if each of G_(1),G_(2),…,G_(n) has at least ((n-1)/2)+2 edges,then{G_(1),G_(2),…,G_(n)}contains a rainbow Hamilton cycle.Moreover,if each of G_(1),G_(2),…,G_(n-1) has at least (n-1)/2)+1 edges,then{G_(1),G_(2),…,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_(1),G_(2),…,G_(n)}does not contain a rainbow Hamilton cycle,then one can apply the shifting operator to G_(1),G_(2),…,G_(n) simultaneously without producing a rainbow Hamilton cycle.By applying the shifting operator to G_(1),G_(2),…,G_(n) repeatedly,eventually we shall obtain a sequence of shifted graphs G_(1),G_(2),…,G_(n).For two pairs(x_(1),x_(2))and(y_(1),y_(2)),define the shifted partial order as:(x_(1),x_(2))(y_(1),y_(2))if and only if either x_(1) y_(1) and x_(2) y_(2) or x_(1) y_(2) and x_(2) y_(1) hold.The shifted graphs have the following nice property:if x_(1)x_(2) is an edge of G and G_(i)s shifted,then for any pair(x_(1),x_(2))(y_(1),y_(2)),y_(1)y_(2) 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={1,2k},f 2={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 1,f 2,…,f 2k form a Hamilton cycle.Since{G_(1),G_(2),…,G_(n)}does not contain a rainbow Hamilton cycle,we infer that there exists i such that f_(i) G_(i).If_(i)=2k,then{1,k+1}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}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}E(G_(i)).Since f_(i) f j={j,2k+1-j},f j 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={1,2k+1},f 2={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_(1),G_(2),…,G_(n)}does not contain a rainbow Hamilton cycle,there exists i such that f_(i) G_(i).If_(i)=2k+1,then{1,k+1}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}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}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 ((n-1)/2)+1 edges,which leads to a contradiction.Thus,we conclude that if each of G_(1),G_(2),…,G_(n) has at least ((n-1)/2)+2 edges,then{G_(1),G_(2),…,G_(n)}contains a rainbow Hamiltonian cycle.By a similar argument,we establish the corresponding result for rainbow Hamiltonian paths as well.