Home » Keyword index

feedback vertex set


Graph Theory » Basic G.T. » Cycles

Jones' conjecture ★★

Author(s): Kloks; Lee; Liu

For a graph $ G $, let $ cp(G) $ denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let $ cc(G) $ denote the cardinality of a minimum feedback vertex set (set of vertices $ X $ so that $ G-X $ is acyclic).

Conjecture   For every planar graph $ G $, $ cc(G)\leq 2cp(G) $.

Keywords: cycle packing; feedback vertex set; planar graph

Posted by cmlee
updated December 5th, 2019
3 comments
Syndicate content