We consider a natural generalization of chordal graphs, in which every minimal separator induces a subgraph with independence number at most $2$. Such graphs can be equivalently defined as graphs that do not contain the complete bipartite graph K2,3 as an induced minor, that is, graphs from which K2,3 cannot be obtained by a sequence of edge contractions and vertex deletions. We develop a polynomial-time algorithm for recognizing these graphs. Our algorithm relies on a characterization of K2,3-induced minor-free graphs in terms of excluding particular induced subgraphs, called Truemper configurations.
No takes yet. Share an insight, caveat, or question.
Dallard et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: