4 papers
(Even hole, triangle)-free graphs revisited
Beatriz Martins, Nicolas Trotignon
We revisit a classical paper about (even hole, triangle)-free graphs [Conforti, Cornuéjols, Kapoor and Vu\v skoviÄ, Triangle-free graphs that are signable without even holes, Jou…
Induced Minor Models. I. Structural Properties and Algorithmic Consequences
Nicolas Bousquet, Clément Dallard, Maël Dumas +4
A graph is said to be an induced minor of a graph if can be obtained from by a sequence of vertex deletions and edge contractions. Equivalently, is an induced m…
Unavoidable induced subgraphs in graphs with complete bipartite induced minors
Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen +2
We prove that if a graph contains the complete bipartite graph as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. W…
Induced Disjoint Paths Without an Induced Minor
Pierre Aboulker, Ãdouard Bonnet, Timothé Picavet +1
We exhibit a new obstacle to the nascent algorithmic theory for classes excluding an induced minor. We indeed show that on the class of string graphs -- which avoids the 1-subdivis…