Detecting \(K_{2,3}\) as an induced minor

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-02
Main Authors: Dallard, Clément, Dumas, Maël, Hilaire, Claire, Milanič, Martin, Perez, Anthony, Trotignon, Nicolas
Format: Article
Language:English
Subjects:
Algorithms
Graph theory
Graphs
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422