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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page