A note on a cycle partition problem

✍ Scribed by Fengli Yang; Elkin Vumar

• Publisher: Elsevier Science
• Year: 2011
• Tongue: English
• Weight: 209 KB
• Volume: 24
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/j.aml.2011.02.003

✦ Synopsis

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.