A note on a cycle partition problem

Let G be any graph, and let c ( G ) denote the circumference of G . If, for every pair c 1 , c 2 of positive integers satisfying c 1 + c 2 = c ( G ) , the vertex set of G admits a partition into two sets V 1 and V 2 such that V i induces a graph of circumference at most c i , i = 1 , 2 , then G is said to be c -partitionable. In [M.H. Nielsen, On a cycle partition problem, Discrete Math. 308 (2008) 6339–6347], it is conjectured that every graph is c -partitionable. In this paper, we verify this conjecture for a graph with a longest cycle that is a dominating cycle. Moreover, we prove that G is c -partitionable if c ( G ) ≥ | V ( G ) | − 3 .