Menu
Let \(\mathcal{P}\) be a graph property and \(G\) a graph. \(G\) is said to be \(\mathcal{P}\)-saturated if \(G\) does not have property \(\mathcal{P}\) but the addition of any edge between non-adjacent vertices of \(G\) results in a graph with property \(\mathcal{P}\). If \(\mathcal{P}\) is a bipartite graph property and \(G\) is a bipartite graph not in \(\mathcal{P}\), but the addition of any edge between non-adjacent vertices in different parts results in a graph in \(\mathcal{P}\), then \(G\) is \(\mathcal{P}\)-bisaturated. We characterize all \(\mathcal{P}\)-saturated graphs, for which \(\mathcal{P}\) is the family of interval graphs, and show that this family is precisely the family of maximally non-chordal graphs. We also present a conjectured characterization of all \(\mathcal{P}\)-bisaturated graphs, in the case where \(\mathcal{P}\) is the family of interval bigraphs, and prove it as far as current forbidden subgraph characterizations allow. We demonstrate that extremal non-interval graphs and extremal non-interval bigraphs are highly related, in that the former is simply a complete graph with \(2K_2\) removed and the latter is a complete bipartite graph with \(3K_2\) removed.