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.05110OpenAlexW1964859857MaRDI 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
Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)
Related Items (38)
Generalizations and strengthenings of Ryser's conjecture ⋮ Vertex covers by monochromatic pieces -- a survey of results and problems ⋮ Monochromatic cycle power partitions ⋮ Partitioning 3-edge-coloured complete bipartite graphs into monochromatic cycles ⋮ Partitioning two-coloured complete multipartite graphs into monochromatic paths and cycles ⋮ Monochromatic Cycle Partitions in Local Edge Colorings ⋮ Monochromatic cycle partitions of graphs with large minimum degree ⋮ Vertex covering with monochromatic pieces of few colours ⋮ Partitioning infinite hypergraphs into few monochromatic Berge-paths ⋮ Cover \(k\)-uniform hypergraphs by monochromatic loose paths ⋮ Improved monochromatic loose cycle partitions in hypergraphs ⋮ Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles ⋮ Partitioning edge-coloured complete graphs into monochromatic cycles and paths ⋮ Monochromatic loose-cycle partitions in hypergraphs ⋮ Almost partitioning 2-edge-colourings of 3-uniform hypergraphs with two monochromatic tight cycles ⋮ Monochromatic paths in 2-edge-coloured graphs and hypergraphs ⋮ Vertex partitions of non-complete graphs into connected monochromatic \(k\)-regular graphs ⋮ Local colourings and monochromatic partitions in complete bipartite graphs ⋮ Monochromatic partitions in local edge colorings ⋮ Minimum degree conditions for monochromatic cycle partitioning ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Partitioning 2-edge-colored graphs by monochromatic paths and cycles ⋮ Coverings by few monochromatic pieces: a transition between two Ramsey problems ⋮ Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\) ⋮ Monochromatic bounded degree subgraph partitions ⋮ Partitioning random graphs into monochromatic components ⋮ Partitioning 2-coloured complete \(k\)-uniform hypergraphs into monochromatic \(\ell\)-cycles ⋮ An Improved Bound for Vertex Partitions by Connected Monochromatic K-Regular Graphs ⋮ Unnamed Item ⋮ Monochromatic cycle partitions of edge-colored graphs ⋮ Partitioning 2-Edge-Colored Ore-Type Graphs by Monochromatic Cycles ⋮ Local colourings and monochromatic partitions in complete bipartite graphs ⋮ Monochromatic square-cycle and square-path partitions ⋮ Monochromatic cycle partitions in random graphs ⋮ Partitioning a graph into a cycle and a sparse graph ⋮ Partitioning Edge-Colored Hypergraphs into Few Monochromatic Tight Cycles ⋮ Towards Lehel's conjecture for 4-uniform tight cycles ⋮ Almost Partitioning a 3-Edge-Colored $K_{n,n}$ into Five Monochromatic Cycles
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
This page was built for publication: Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture
