A graph H is an induced minor of G if there exists an induced minor model of H in G , that is, a collection of pairwise disjoint subsets of vertices of G labeled by the vertices of H , each inducing a connected subgraph in G , such that two vertices of H are adjacent if and only if there is an edge in G between the corresponding subsets. In this paper, we investigate structural properties of induced minor models, including bounds on treewidth and chromatic number of the subgraphs induced by minimal induced minor models. As algorithmic applications of our structural results, we make use of recent developments regarding tree-independence number to show that if H is the 4-wheel, the 5-vertex complete graph minus an edge, or a complete bipartite graph K 2 , q , then there is a polynomial-time algorithm to find in a given graph G an induced minor model of H in G , if there is one. We also develop an alternative polynomial-time algorithm for recognizing graphs that do not contain K 2 , 3 as an induced minor, which revolves around the idea of detecting the induced subgraphs whose presence is forced when the input graph contains K 2 , 3 as an induced minor. It turns out that all these induced subgraphs are Truemper configurations.

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-subdivision of, say, $K_5$ as an induced minor -- Induced 2-Disjoint Paths is NP-complete. So, while $k$-Disjoint Paths, for a fixed $k$, is polynomial-time solvable in general graphs, the absence of a graph as an induced minor does not make its induced variant tractable, even for $k=2$. This answers a question of Korhonen and Lokshtanov [SODA '24], and complements a polynomial-time algorithm for Induced $k$-Disjoint Paths in classes of bounded genus by Kobayashi and Kawarabayashi [SODA '09]. In addition to being string graphs, our produced hard instances are subgraphs of a constant power of bounded-degree planar graphs, hence have bounded twin-width and bounded maximum degree. We also leverage our new result to show that there is a fixed subcubic graph $H$ such that deciding if an input graph contains $H$ as an induced subdivision is NP-complete. Until now, all the graphs $H$ for which such a statement was known had a vertex of degree at least 4. This answers a question by Chudnovsky, Seymour, and the fourth author [JCTB '13], and by Le [JGT '19]. Finally we resolve another question of Korhonen and Lokshtanov by exhibiting a subcubic graph $H$ without two adjacent degree-3 vertices and such that deciding if an input $n$-vertex graph contains $H$ as an induced minor is NP-complete, and unless the Exponential-Time Hypothesis fails, requires time $2^{Ω(\sqrt n)}$. This complements an algorithm running in subexponential time $2^{O(n^{2/3} \log n)}$ by these authors [SODA '24] under the same technical condition.

Abstract. We prove that if a graph contains the complete bipartite graph [Formula: see text] as an induced minor, then it contains a cycle of length at most 12 or a theta as an induced subgraph. With a longer and more technical proof, we prove that if a graph contains [Formula: see text] as an induced minor, then it contains a triangle or a theta as an induced subgraph. Here, a theta is a graph made of three internally vertex-disjoint chordless paths [Formula: see text], [Formula: see text], [Formula: see text], each of length at least two, such that no edges exist between the paths except the three edges incident to [Formula: see text] and the three edges incident to [Formula: see text]. A consequence is that excluding a grid and a complete bipartite graph as induced minors is not enough to guarantee a bounded tree-independence number or even that the treewidth is bounded by a function of the size of the maximum clique, because the existence of graphs with large treewidth that contain no triangles or thetas as induced subgraphs is already known (the so-called layered wheels).

The class of even-hole-free graphs is very similar to the class of perfect graphs, and was indeed a cornerstone in the tools leading to the proof of the Strong Perfect Graph Theorem. However, the complexity of computing a maximum independent set (MIS) is a long-standing open question in even-hole-free graphs. From the hardness point of view, MIS is W[1]-hard in the class of graphs without induced 4-cycle (when parameterized by the solution size). Halfway of these, we show in this paper that MIS is FPT when parameterized by the solution size in the class of even-hole-free graphs. The main idea is to apply twice the well-known technique of augmenting graphs to extend some initial independent set.

An ISK4 in a graph G is an induced subgraph of G that is isomorphic to a subdivision of $$K_4$$ (the complete graph on four vertices). A wheel is a graph that consists of a chordless cycle, together with a vertex that has at least three neighbors in the cycle. A graph is {ISK4,wheel}-free if it has no ISK4 and does not contain a wheel as an induced subgraph. We give an $$O(|V(G)|^7)$$ -time algorithm to compute the maximum weight of a stable set in an input weighted {ISK4,wheel}-free graph G with non-negative integer weights.

We prove that any graph $G$ of minimum degree greater than $2k^2-1$ has a $(k+1)$-connected induced subgraph $H$ such that the number of vertices of $H$ that have neighbors outside of $H$ is at most $2k^2-1$. This generalizes a classical result of Mader, which states that a high minimum degree implies the existence of a highly connected subgraph. We give several variants of our result, and for each of these variants, we give asymptotics for the bounds. We also compute optimal values for the case when $k=2$. Alon, Kleitman, Saks, Seymour, and Thomassen proved that in a graph of high chromatic number, there exists an induced subgraph of high connectivity and high chromatic number. We give a new proof of this theorem with a better bound.

We recall several known results about minimally 2-connected graphs and show that they all follow from a decomposition theorem. Starting from an analogy with critically 2-connected graphs, we give structural characterizations of the classes of graphs that do not contain as a subgraph and as an induced subgraph, a cycle with a node that has at least two neighbors on the cycle. From these characterizations we get polynomial time recognition algorithms for these classes and polynomial time algorithms for vertex-coloring and edge-coloring.

We consider the class of graphs containing no odd hole, no odd antihole, and no configuration consisting of three paths between two nodes such that any two of the paths induce a hole, and at least two of the paths are of length 2. This class generalizes claw-free Berge graphs and square-free Berge graphs. We give a combinatorial algorithm of complexity $O(n^{7})$ to find a clique of maximum weight in such a graph. We also consider several subgraph-detection problems related to this class.

We consider the class ${\cal A}$ of graphs that contain no odd hole, no antihole of length at least 5, and no prism (a graph consisting of two disjoint triangles with three disjoint paths between them) and the class ${\cal A}'$ of graphs that contain no odd hole, no antihole of length at least 5, and no odd prism (prism whose three paths are odd). These two classes were introduced by Everett and Reed and are relevant to the study of perfect graphs. We give polynomial-time recognition algorithms for these two classes. In contrast we prove that determining if a general graph contains a prism (or an even prism, or an odd prism) is NP-complete.