Partitioning a graph into a cycle and a sparse graph

DOI10.1016/J.DISC.2022.113161MaRDI QIDQ2092387zbMATH OpenOpenAlexFDO

Authors Alexey Pokrovskiy

Publication date 2 November 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1607.03348

zbMATH Keywords

cyclespartitioning graphsRamsey theory

Mathematics Subject Classification ID

Paths and cycles (05C38) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Ramsey theory (05D10)

Abstract: In this paper we investigate results of the form "every graph $G$ has a cycle $C$ such that the induced subgraph of $G$ on $V(G)setminusV(C)$ has small maximum degree." Such results haven't been studied before, but are motivated by the Bessy and Thomass'e Theorem which states that the vertices of any graph $G$ can be covered by a cycle $C_1$ in $G$ and disjoint cycle $C_2$ in the complement of $G$. There are two main theorems in this paper. The first is that every graph has a cycle with $Delta(G[V(G)setminusV(C)])leqfrac12(|V(G)setminusV(C)|-1)$. The bound on the maximum degree $Delta(G[V(G)setminusV(C)])$ is best possible. The second theorem is that every $k$-connected graph $G$ has a cycle with $Delta(G[V(G)setminusV(C)])leqfrac1k+1|V(G)setminusV(C)|+3$. We also give an application of this second theorem to a conjecture about partitioning edge-coloured complete graphs into monochromatic cycles.

Recommendations

• Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\)
• Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture
• Monochromatic cycle partitions of edge-colored graphs
• scientific article; zbMATH DE number 2094820
• Minimum degree conditions for monochromatic cycle partitioning

Cites work

• A note on Hamiltonian circuits
• Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles
• scientific article; zbMATH DE number 15152 (Why is no real title available?)
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• scientific article; zbMATH DE number 3353327 (Why is no real title available?)
• Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\)
• Monochromatic cycle partitions of graphs with large minimum degree
• Note on Hamilton Circuits
• Partitioning 2-edge-colored graphs by monochromatic paths and cycles
• Partitioning 3-colored complete graphs into three monochromatic cycles
• Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles
• The size Ramsey number of a directed path
• Vertex coverings by monochromatic cycles and trees
• Vertex coverings by monochromatic paths and cycles

Cited in

(10)

• Towards Lehel's conjecture for 4-uniform tight cycles
• Cycle partition of two-connected and two-edge connected graphs
• Monochromatic paths in 2-edge-coloured graphs and hypergraphs
• Partitioning a graph into two square-cycles
• Almost partitioning a 3-edge-colored \(K_{n,n}\) into five monochromatic cycles
• Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
• Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\)
• Polynomial bounds for monochromatic tight cycle partition in \(r\)-edge-coloured \(K_n^{(k)}\)
• Almost partitioning every 2-edge-coloured complete k-graph into k monochromatic tight cycles
• Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture

This page was built for publication: Partitioning a graph into a cycle and a sparse graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2092387)