The size of chordal, interval and threshold subgraphs (Q1812749)

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=n^2/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 \(n^2/3\) edges.