Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture
From MaRDI portal
Publication:965246
DOI10.1016/j.jctb.2009.07.001zbMath1216.05110MaRDI QIDQ965246
Steéphan Thomassé, Stéphane Bessy
Publication date: 21 April 2010
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-00512762/file/lehel.pdf
05C38: Paths and cycles
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C15: Coloring of graphs and hypergraphs
Related Items
An Improved Bound for Vertex Partitions by Connected Monochromatic K-Regular Graphs, Almost Partitioning a 3-Edge-Colored $K_{n,n}$ into Five Monochromatic Cycles, Local colourings and monochromatic partitions in complete bipartite graphs, Local colourings and monochromatic partitions in complete bipartite graphs, Vertex covers by monochromatic pieces -- a survey of results and problems, Partitioning 3-edge-coloured complete bipartite graphs into monochromatic cycles, Partitioning two-coloured complete multipartite graphs into monochromatic paths and cycles, Monochromatic cycle partitions of graphs with large minimum degree, Improved monochromatic loose cycle partitions in hypergraphs, Partitioning edge-coloured complete graphs into monochromatic cycles and paths, Monochromatic loose-cycle partitions in hypergraphs, Partitioning 2-edge-colored graphs by monochromatic paths and cycles, Coverings by few monochromatic pieces: a transition between two Ramsey problems, Monochromatic bounded degree subgraph partitions, Partitioning random graphs into monochromatic components, Vertex partitions of non-complete graphs into connected monochromatic \(k\)-regular graphs, Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\), Vertex covering with monochromatic pieces of few colours, Almost partitioning 2-edge-colourings of 3-uniform hypergraphs with two monochromatic tight cycles, Partitioning 2-coloured complete \(k\)-uniform hypergraphs into monochromatic \(\ell\)-cycles, Partitioning infinite hypergraphs into few monochromatic Berge-paths, Monochromatic cycle power partitions, Cover \(k\)-uniform hypergraphs by monochromatic loose paths, Unnamed Item, Partitioning 2-Edge-Colored Ore-Type Graphs by Monochromatic Cycles, Monochromatic cycle partitions of edge-colored graphs, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Monochromatic Cycle Partitions in Local Edge Colorings
Cites Work
- An improved bound for the monochromatic cycle partition number
- Vertex coverings by monochromatic cycles and trees
- Partitioning complete bipartite graphs by monochromatic cycles
- Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles
- Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles
- Vertex coverings by monochromatic paths and cycles
