Requiring that Minimal Separators Induce Complete Multipartite Subgraphs

Abstract

Complete multipartite graphs range from complete graphs (with every partite set a singleton) to edgeless graphs (with a unique partite set). Requiring minimal separators to all induce one or the other of these extremes characterizes, respectively, the classical chordal graphs and the emergent unichord-free graphs. New theorems characterize several subclasses of the graphs whose minimal separators induce complete multipartite subgraphs, in particular the graphs that are 2-clique sums of complete, cycle, wheel, and octahedron graphs.

Keywords

• minimal separator
• complete multipartite graph
• chordal graph
• unichord-free graph
• 05c62
• 05c75
• 05c69