×

zbMATH — the first resource for mathematics

Outerplanar obstructions for the feedback vertex set. (English) Zbl 1273.05213
Nešetřil, Jaroslav (ed.) et al., Extended abstracts of the 5th European conference on combinatorics, graph theory and applications, EuroComb’09, Bordeaux, France, September 7–11, 2009. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 34, 167-171 (2009).
Summary: For \(k\geq 1\), let \({\mathcal{F}}_{k}\) be the class containing every graph that contains \(k\) vertices meeting all its cycles. The minor-obstruction set for \({\mathcal{F}}_{k}\) is the set \(\mathsf{obs}(F_{k})\) containing all minor-minimal graph that does not belong to \({\mathcal{F}}_{k}\). We denote by \({\mathcal{Y}}_{k}\) the set of all outerplanar graphs in \(\mathsf{obs}({\mathcal{F}}_{k})\). In this paper, we provide a precise characterization of the class \({\mathcal{Y}}_{k}\). Then, using the symbolic method, we prove that \(|{\mathcal{Y}}_{k}| \sim \alpha \cdot k^{-5/2} \cdot \rho ^{-k}\) where \(\alpha \doteq 0.02602193\) and \(\rho^{-1} \doteq 14.49381704\).
For the entire collection see [Zbl 1239.05008].

MSC:
05C83 Graph minors
05C30 Enumeration in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bergeron, F.; Labelle, G.; Leroux, P., Combinatorial species and tree-like structures, Encyclopedia of mathematics and its applications, volume 67, (1998), Cambridge University Press Cambridge, foreword by Gian-Carlo Rota · Zbl 0888.05001
[2] M.J. Dinneen. Too many minor order obstructions (for parameterized lower ideals). In Proceedings of the First Japan-New Zealand Workshop on Logic in Computer Science (Auckland, 1997), volume 3(11), pages 1199-1206 (electronic), 1997 · Zbl 0967.68117
[3] Dinneen, M.J.; Cattell, K.; Fellows, M.R., Forbidden minors to graphs with small feedback sets, Discrete math., 230, 1-3, 215-252, (2001), Paul Catlin memorial collection (Kalamazoo, MI, 1996) · Zbl 0964.05064
[4] Flajolet, P.; Sedgewick, R., Analytic combinatorics, (2008), Cambridge Univ. Press
[5] M.F.M.J. Dinneen, K. Cattell. Forbidden minors to graphs with small feedback sets. Technical Report Report CDMTCS-019, Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland, New Zealand, October 1996. See http://www.cs.auckland.ac.nz/CDMTCS/researchreports/019mjd.pdf · Zbl 0964.05064
[6] Parsons, T.D., The search number of a connected graph, (), 549-554
[7] Robertson, N.; Seymour, P.D., Graph minors. XX. Wagner’s conjecture, J. combin. theory ser. B, 92, 2, 325-357, (2004) · Zbl 1061.05088
[8] Takahashi, A.; Ueno, S.; Kajitani, Y., Minimal acyclic forbidden minors for the family of graphs with bounded path-width, Discrete mathematics, 127, 1/3, 293-304, (1994) · Zbl 0795.05123
[9] Thilikos, D.M., Algorithms and obstructions for linear-width and related search parameters, Discrete applied mathematics, 105, 239-271, (2000) · Zbl 0958.05124
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.