Outerplanar Obstructions for the Feedback Vertex Set

Juanjo Rué, Konstantinos S. Stavropoulos, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


For k ≥ 1, let Fk be the class containing every graph that contains k vertices meeting all its cycles. The minor-obstruction set for Fk is the set obs (Fk) containing all minor-minimal graph that does not belong to Fk. We denote by Yk the set of all outerplanar graphs in obs (Fk). In this paper, we provide a precise characterization of the class Yk. Then, using the symbolic method, we prove that | Yk | ∼ α ṡ k- 5 / 2 ṡ ρ- k where α {approaches the limit} 0.02602193 and ρ- 1 {approaches the limit} 14.49381704.

Original languageEnglish (US)
Pages (from-to)167-171
Number of pages5
JournalElectronic Notes in Discrete Mathematics
StatePublished - Aug 1 2009


  • feedback vertex set
  • graph enumeration
  • Graph minors
  • obstructions
  • outerplanar graphs
  • singularity analysis

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Outerplanar Obstructions for the Feedback Vertex Set'. Together they form a unique fingerprint.

Cite this