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.
@article{bwmeta1.element.doi-10_7151_dmgt_1988,
author = {Terry A. McKee},
title = {Requiring that Minimal Separators Induce Complete Multipartite Subgraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {38},
year = {2018},
pages = {263-273},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1988}
}
Terry A. McKee. Requiring that Minimal Separators Induce Complete Multipartite Subgraphs. Discussiones Mathematicae Graph Theory, Tome 38 (2018) pp. 263-273. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1988/