Name
Abstract | ||
|---|---|---|
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 Luczak, Rodl and Szemeredi [T. Luczak, V. Rodl, E. Szemeredi, 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]. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.jctb.2009.07.001 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
v. rodl,monochromatic cycle,disjoint monochromatic cycle,two-colored complete graph,e. szemeredi,t. luczak,large graph,graph partition,two-edge-coloured complete graph,p. allen,graph g,cycle decomposition,graph partitioning,edge coloring,complete graph | Discrete mathematics,Combinatorics,Chordal graph,Cycle decomposition,Cycle graph,Cograph,Pathwidth,1-planar graph,Mathematics,Pancyclic graph,Split graph | Journal |
Volume | Issue | ISSN |
100 | 2 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
27 | 1.51 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Bessy | 1 | 117 | 19.68 |
| Stéphan Thomassé | 2 | 651 | 66.03 |