Browsing by Author "Shih, Chie-Huai"

Now showing 1 - 1 of 1

FEEDBACK VERTEX SET ON PLANAR GRAPHS
(2012-12-01)
Chen, Hong-Bin
;
Fu, Hung-Lin
;
Shih, Chie-Huai
;
應用數學系
;
Department of Applied Mathematics
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.