Pim van 't Hof

Maximum number of minimal feedback vertex sets in chordal graphs and cographs

Jean-François Couturier, Pinar Heggernes, Pim van 't Hof and Yngve Villanger

This paper appeared in the proceedings of COCOON 2012, the 18th Annual International Computing and Combinatorics Conference (held on August 20-22, 2012 in Sydney, Australia), Lecture Notes in Computer Science, vol. 7434, pp. 204-215, 2012.
[DOI]

Abstract:

A feedback vertex set in a graph is a set of vertices whose removal leaves the remaining graph acyclic. Given the vast number of published results concerning feedback vertex sets, it is surprising that the related combinatorics appears to be so poorly understood. The maximum number of minimal feedback vertex sets in a graph on n vertices is known to be at most 1.864ⁿ. However, no examples of graphs having 1.593ⁿ or more minimal feedback vertex sets are known, which leaves a considerable gap between these upper and lower bounds on general graphs. In this paper, we close the gap completely for chordal graphs and cographs, two famous perfect graph classes that are not related to each other. We prove that for both of these graph classes, the maximum number of minimal feedback vertex sets is 10^n/5 ≈ 1.585ⁿ, and there is a matching lower bound.