Edge Maximal Non-Interval Graphs

Abstract

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.