On cycle packings and feedback vertex sets

For a graph G, let fvs and cp denote the minimum size of a feedback vertex set in G and the maximum size of a cycle packing in G, respectively. Kloks, Lee, and Liu conjectured that fvs(G)≤2cp(G) if G is planar. They proved a weaker inequality, replacing 2 by 5. We improve this, replacing 5 by 3, and verifying the resulting inequality for graphs embedded in surfaces of nonnegative Euler characteristic. We also generalize to arbitrary surfaces. We show that, if a graph G embeds in a surface of Euler characteristic c≤0, then fvs(G)≤3cp(G)+103(−c). Lastly, we consider what the best possible bound on fvs might be, and give some open problems.

• Publication year

  2014

• Venue

  Contributions Discret. Math.

• Publication date

  2014-12-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.11575/cdm.v9i2.62105
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Locally grid graphs: classification and Tutte uniqueness

  2003cited by this paper
• New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k -Disjoint Cycles on Plane and Planar Graphs

  2002cited by this paper
• Graphs on Surfaces

  2001cited by this paper
• Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface

  1991cited by this paper
• Orientably simple graphs

  1987cited by this paper
• On Independent Circuits Contained in a Graph

  1965cited by this paper

• Jones’ Conjecture for Halin Graphs and a Bit More

  2024cites this paper
• Jones' Conjecture in subcubic graphs

  2019cites this paper
• On line graphs of subcubic triangle-free graphs

  2017cites this paper
• Sur quelques invariants classiques et nouveaux des hypergraphes

  2016influential citation
• On some classical and new hypergraph invariants

  2016influential citation