Authors:
T.A. McKee
Title:
Requiring that minimal separators induce complete multipartite subgraphs
Source:
Discussiones Mathematicae Graph Theory
Received 28.06.2016, Revised 09.11.2016, Accepted 09.11.2016, doi: 10.7151/dmgt.1988

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

Links:
PDF