1. Detecting $K_{2,3}$ as an induced minor
- Author
-
Dallard, Clément, Dumas, Maël, Hilaire, Claire, Milanič, Martin, Perez, Anthony, and Trotignon, Nicolas
- Subjects
Mathematics - Combinatorics ,Computer Science - Discrete Mathematics ,Computer Science - Data Structures and Algorithms ,05C75 (Primary), 05C85, 05C83, 05C40, 05C69 (Secondary) - Abstract
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 $K_{2,3}$ as an induced minor, that is, graphs from which $K_{2,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 $K_{2,3}$-induced minor-free graphs in terms of excluding particular induced subgraphs, called Truemper configurations., Comment: 18 pages
- Published
- 2024