2016/07/12 by Pokrovskiy, Alexey
#05C38 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1607.03348
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)])≤ \frac12(|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)])≤ \frac1k+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.