Feedback vertex set on planar graphs

Hong Bin Chen*, Hung-Lin Fu, Chie Huai Shih

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

A feedback vertex set of a graph is a set of vertices whose removal results an acyclic graph. This paper shows that for every planar graph the minimum cardinality of a feedback vertex set is at most three times the maximum number of vertex disjoint cycles in the graph.

Original languageEnglish
Pages (from-to)2077-2082
Number of pages6
JournalTaiwanese Journal of Mathematics
Volume16
Issue number6
DOIs
StatePublished - 1 Jan 2012

Keywords

  • Cycle packing number
  • Feedback vertex set
  • Vertex disjoint cycle

Fingerprint Dive into the research topics of 'Feedback vertex set on planar graphs'. Together they form a unique fingerprint.

  • Cite this