Graphs of separability at most 2

We introduce graphs of separability at most  kk as graphs in which every two non-adjacent vertices are separated by a set of at most kk other vertices. Graphs of separability at most kk arise in connection with the Parsimony Haplotyping problem from computational biology. For k∈{0,1}k∈{0,1}, the only connected graphs of separability at most kk are complete graphs and block graphs, respectively. For k≥3k≥3, graphs of separability at most kk form a rich class of graphs containing all graphs of maximum degree kk.We prove several characterizations of graphs of separability at most 2, which generalize complete graphs, cycles and trees. The main result is that every connected graph of separability at most 2 can be constructed from complete graphs and cycles by pasting along vertices or edges, and vice versa, every graph constructed this way is of separability at most 2. The structure theorem has nice algorithmic implications—some of which cannot be extended to graphs of higher separability—however certain optimization problems remain intractable on graphs of separability 2. We then characterize graphs of separability at most 2 in terms of minimal forbidden induced subgraphs and minimal forbidden induced minors. Finally, we discuss the possibilities of extending these results to graphs of higher separability.