Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 534.05037
Autor: Erdös, Paul; Laskar, Renu
Title: On maximum chordal subgraph. (In English)
Source: Combinatorics, graph theory and computing, Proc. 14th Southeast. Conf., Boca Raton/Flo. 1983, Congr. Numerantium 39, 367-373 (1983).
Review: [For the entire collection see Zbl 523.00001.]
Let f(n) be the smallest integer such that every graph G on n vertices can be made chordal by deleting at most f(n) edges of G. The result of this paper is that f(n) = \frac{n2}{2}-(1+o(1))\sqrt{2}n3/2.
Reviewer: D.de Caen
Classif.: * 05C35 Extremal problems (graph theory)
Keywords: chordal graph; deleting edges
Citations: Zbl 523.00001
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag