Pokrovskiy, Alexey; (2023) Partitioning a graph into a cycle and a sparse graph. Discrete Mathematics , 346 (1) , Article 113161. 10.1016/j.disc.2022.113161.

Preview

PDF 1-s2.0-S0012365X22003673-main.pdf - Published Version Download (788kB) | Preview

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) \ V (C) has small maximum degree.” Such results haven’t been studied before, but are motivated by the Bessy and Thomassé Theorem which states that the vertices of any graph G can be covered by a cycle C1 in G and disjoint cycle C2 in the complement of G. There are two main theorems in this paper. The first is that every graph has a cycle with (G[V (G) \ V (C)]) ≤ 1 2 (|V (G) \ V (C)| − 1). The bound on the maximum degree (G[V (G) \ V (C)]) is best possible. The second theorem is that every k-connected graph G has a cycle with (G[V (G) \ V (C)]) ≤ 1 k+1 |V (G) \ V (C)| + 3. We also give an application of this second theorem to a conjecture about partitioning edge-coloured complete graphs into monochromatic cycles

Download activity - last month

Export as CSVXMLJSON

Download activity - last 12 months

Export as JSONXMLCSV

Downloads by country - last 12 months

Export as JSONXMLCSV

Archive Staff Only

View Item