Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 738.05051
Autor: Erdös, Paul; Gyárfás, A.; Ordman, E.T.; Zalcstein, Y.
Title: The size of chordal, interval and threshold subgraphs. (In English)
Source: Combinatorica 9, No.3, 245-253 (1989).
Review: A graph is chordal if no set of four or more vertices induces a cycle. A proper subclass of these graphs is formed by the interval graphs which in turn strictly contains the class of threshold graphs. Each of these three classes is closed under the operation of taking induced subgraphs.
The authors consider the following question: given a graph G with n vertices and m edges, how many edges must there be in the largest chordal (resp. interval, resp. threshold) subgraph of G. If m = n2/4+1 they show that G contains a chordal graph with at least 3n/2-1 edges. Analogous results are obtained for interval and threshold graphs. Some results are also obtained for graphs with n vertices and exactly n2/3 edges.
Reviewer: C.Godsil (Waterloo / Ontario)
Classif.: * 05C35 Extremal problems (graph theory)
Keywords: interval graphs; threshold graphs; chordal graph
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag