Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture

详细信息    查看全文

• 作者：Sté ; phane Bessy ; Sté ; phan Thomassé
• 关键词：Graph partition ; Two-colored complete graph ; Cycle decomposition
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2010
• 出版时间：March 2010
• 年：2010
• 卷：100
• 期：2
• 页码：176-180
• 全文大小：124 K

文摘

We prove that every graph G has a vertex partition into a cycle and an anticycle (a cycle in the complement of G). Emptyset, singletons and edges are considered as cycles. This problem was posed by Lehel and shown to be true for very large graphs by Łuczak, Rödl and Szemerédi [T. Łuczak, V. Rödl, E. Szemerédi, Partitioning two-colored complete graphs into two monochromatic cycles, Combin. Probab. Comput. 7 (1998) 423–436], and more recently for large graphs by Allen [P. Allen, Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles, Combin. Probab. Comput. 17 (2008) 471–486].