# Unavoidable Induced Subgraphs in Graphs with Complete Bipartite Induced Minors

Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen, Nicolas Trotignon, Sebastian Wiederrecht

► To cite this version:

Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen, Nicolas Trotignon, Sebastian Wiederrecht. Unavoidable Induced Subgraphs in Graphs with Complete Bipartite Induced Minors. SIAM Journal on Discrete Mathematics, 2025, 39 (4), pp.2049-2066. 10.1137/24M1660437. hal-05359637

HAL Id: hal-05359637

https://hal.science/hal-05359637v1

Submitted on 12 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Unavoidable induced subgraphs in graphs with complete bipartite induced minors

Maria Chudnovsky¹, Meike Hatzel², Tuukka Korhonen³, Nicolas Trotignon⁴, and Sebastian Wiederrecht⁵

¹Princeton University, Princeton, NJ 08544, USA

²Discrete Mathematics Group, Institute for Basic Science, Daejeon, South Korea

³University of Copenhagen, Denmark

⁴CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP, UMR 5668, Lyon, France

⁵KAIST, Daejeon, South Korea

September 9, 2025

## Abstract

We prove that if a graph contains the complete bipartite graph $K_{134,12}$ 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 $K_{3,4}$ 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 $P_1 = a...b, P_2 = a...b, P_3 = a...b$, each of length at least two, such that no edges exist between the paths except the three edges incident to *a* and the three edges incident to *b*.

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).
# 1 Introduction

Graphs in this paper are finite and simple. A graph $H$ is an *induced subgraph* of a graph $G$ if $H$ can be obtained from $G$ be repeatedly deleting vertices. It is an *induced minor* of $G$ if $H$ can be obtained from $G$ be repeatedly deleting vertices and contracting edges. It is a *minor* of $G$ if $H$ can be obtained from $G$ be repeatedly deleting vertices, deleting edges and contracting edges. We denote by $K_t$ the complete graph on $t$ vertices and by $K_{a,b}$ the complete bipartite graph with sides of size $a$ and $b$. The $(k \times k)$-grid is the graph whose vertices are the pairs $(i, j)$ of integers such that $1 \le i, j \le k$ and where $(i, j)$ is adjacent to $(i', j')$ if and only if $|i - i'| + |j - j'| = 1$.

The tree-independence number was introduced in [3]. It is defined via tree-decompositions similarly to treewidth, except that the number associated to each bag of a tree-decomposition is the maximum size of an independent set of the graph induced by the bag, instead of its number of vertices (we omit the full definition for the sake of brevity). It attracted some attention lately, in particular because for each class of graphs with bounded tree-independence number, there exists polynomial time algorithms for maximum independent set and other related problems [3, 5, 6, 11].

The celebrated grid minor theorem of Robertson and Seymour [7] states that there exists a function $f: \mathbb{N} \to \mathbb{N}$ so that any graph with treewidth at least $f(k)$ contains a $(k \times k)$-grid as a minor. The motivation for our work is the quest for a similar theorem with “tree-independence number” instead of “treewidth”.

Here, the natural containment relation should be “induced minor” instead of “minor”, since the tree-independence number is monotone under taking induced minors but not under taking minors. The following lemma shows that for triangle-free graphs, treewidth and tree-independence number are essentially equivalent.

**Lemma 1.1** (see [3]). The treewidth of a triangle-free graph with tree-independence number at most $t$ is at most $R(3, t + 1) - 2$ where $R(a, b)$ denotes the classical Ramsey number.

By Lemma 1.1, grids and complete bipartite graphs have unbounded tree-independence number. The list of unavoidable graphs arising from a large tree-independence number should therefore contain at least large grids and large complete bipartite graphs. Our main result is that this list is not complete. Indeed, we prove that a construction called *layered wheel*, first defined in [8], contains no (5 × 5)-grid and no $K_{3,4}$ as an induced minor, while having arbitrarily large tree-independence number.
## Outline of the proof

To avoid too heavy notation, we allow some abuse. Typically, we do not distinguish between a set of vertices in graph $G$ and the subgraph of $G$ that it induces. For instance, when $P$ is a path and $v$ is a vertex in a graph $G$, we denote by $P \setminus v$ either $V(P) \setminus \{v\}$ or $G[V(P) \setminus \{v\}]$. Also, we may say that a set of vertices $C$ of $G$ is *connected* when the correct statement should be that $G[C]$ is connected. We hope that this improves the readability without causing any confusion.

We do not need to define layered wheels, which is good since the definition is a bit long. We just need some of their properties and some preliminary definitions to state them. A *theta* is a graph made of three internally vertex-disjoint chordless paths $P_1 = a \dots b, P_2 = a \dots b, P_3 = a \dots b$, each of length at least two, such that no edges exist between the paths except the three edges incident to $a$ and the three edges incident to $b$. A graph is *theta-free* if it does not contain a theta as an induced subgraph, and more generally, a graph is *H-free* whenever it does not contain $H$ (when $H$ is a graph) or any graph in $H$ (when $H$ is a class of graphs, such as thetas) as an induced subgraph. The only property of layered wheels that we need is the following theorem that states their existence.

**Theorem 1.2** (see [8]). For all integers $t \ge 1$ and $k \ge 3$, there exists a theta-free graph of girth $k$ that contains $K_t$ as a minor.

Since containing $K_t$ as a minor implies having treewidth at least $t$, layered wheels provide theta-free graphs of arbitrarily large girth and treewidth. Their tree-independence number is also arbitrarily large by Lemma 1.1. To fulfill our goal, it therefore remains to prove that layered wheels do not contain large grids or complete bipartite graphs as induced minors. As far as we can see, this is non-trivial because even if layered wheels are precisely defined, checking directly that they do not contain some $(k \times k)$-grid or $K_{r,s}$ as an induced minor seems to be tedious, at least according to our several attempts. An indication of this is that some layered wheels do contain $K_{3,3}$ as an induced minor, which is not obvious, see Fig. 1 (this figure is meaningful only with the precise definition of a layered wheel).

Our approach is therefore less direct: we study what induced subgraphs are forced by the presence of a large grid or complete bipartite graph as an induced minor as we explain now.
<figure><img src="image_2.png" /><figcaption>Figure 1: A $K_{3,3}$ induced minor in a layered wheel</figcaption></figure>

**Complete bipartite graphs**

The list of induced subgraphs forced by the presence of $K_{2,3}$ as an induced minor is already known and not very difficult to obtain, see [4]. But this is not enough for our purpose since containing $K_{2,3}$ as an induced minor does not imply anything we can use. By a short argument, we first prove the following.

**Theorem 1.3.** If a graph $G$ contains $K_{134,12}$ as an induced minor, then $G$ contains a cycle of length at most 12 or a theta as an induced subgraph.

The advantage of Theorem 1.3 is its short proof. But its statement is far from being optimal, as shown by the following, that we obtain by a more careful structural study.

**Theorem 1.4.** If a graph $G$ contains $K_{3,4}$ as an induced minor, then $G$ contains a triangle or a theta as an induced subgraph.

Once Theorem 1.3 (or 1.4) is proved, checking that layered wheels contain no $K_{134,12}$ (or no $K_{3,4}$) as an induced minor becomes trivial since by Theorem 1.2, they do not contain short cycles and thetas as induced subgraphs. Our results therefore avoid some tedious checking, but we also believe that they are of independent interest.

Note that Theorem 1.4 is best possible in several ways. First, thetas need to be excluded because the subdivisions of $K_{3,4}$ provide triangle-free graphs that obviously contain $K_{3,4}$ as an induced minor while containing
thetas and no triangles. Triangles must be excluded because of line graphs of subdivisions of $K_{3,4}$, see Fig. 2 where the line graph of the graph obtained by subdividing each edge of $K_{3,4}$ is represented: it is a theta-free graph that obviously contains $K_{3,4}$ as an induced minor. A less obvious construction is represented in Fig. 3, showing that $K_{3,4}$ cannot be replaced by $K_{3,3}$ in Theorem 1.4. Also, for all $\ell \ge 1$, there exist (theta, triangle)-free graphs that contain $K_{2,\ell}$ as an induced minor, see Fig. 4

<figure><img src="image_3.png" /><figcaption>Figure 2: The line graph of the graph obtained by subdividing each edge of $K_{3,4}$</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 3: A (triangle, theta)-free graph containing $K_{3,3}$ as an induced minor</figcaption></figure>

In fact, we prove a more general result than Theorem 1.4. Before stating it, we need some definitions.

A *prism* is a graph made of three vertex-disjoint chordless paths $P_1 = a_1 \dots b_1$, $P_2 = a_2 \dots b_2$, $P_3 = a_3 \dots b_3$, such that $\{a_1, a_2, a_3\}$ and $\{b_1, b_2, b_3\}$ are triangles and no edges exist between the paths except those of the two triangles and either:
<figure><img src="image_5.png" /><figcaption>Figure 4: A (theta, triangle)-free graph containing $K_{2,l}$ as an induced minor</figcaption></figure>

• $P_1, P_2$ and $P_3$ all have length at least 1, or

• one of $P_1, P_2, P_3$ has length 0 and each of the other two has length at least 2.

Note that allowing a path of length zero in prisms (for instance if $a_1 = b_1$) is not standard, but natural in our context. A prism with a path of length zero is sometimes referred to as a *line wheel*, but we do not use this terminology here.

<figure><img src="image_6.png" /><figcaption>Figure 5: The different 3-path configurations</figcaption></figure>

A *pyramid* is a graph made of three chordless paths $P_1 = a \dots b_1$, $P_2 = a \dots b_2$, $P_3 = a \dots b_3$, each of length at least one, and two of them with length at least two, vertex-disjoint except at *a*, and such that $\{b_1, b_2, b_3\}$ is
a triangle and no edges exist between the paths except those of the triangle
and the three edges incident to a.

A *hole* in a graph is a chordless cycle of length at least 4. A graph that is either a theta, a prism or a pyramid is called a *3-paths configuration*, or *3PC* for short. Observe that a graph *G* is a 3PC if and only if there exist three pairwise internally vertex disjoint paths *P*₁, *P*₂, *P*₃ such that *V*(*G*) = *V*(*P*₁) ∪ *V*(*P*₂) ∪ *V*(*P*₃) and for every distinct *i*, *j* ∈ {1, 2, 3}, *V*(*P*ᵢ) ∪ *V*(*P*ⱼ) induces a hole.

**Theorem 1.5.** If a graph *G* contains *K*<sub>3,4</sub> as an induced minor, then *G* contains a 3PC as an induced subgraph.

Theorem 1.5 clearly implies Theorem 1.4 because a 3PC that is not a
theta contains a triangle. Proving Theorem 1.5 is just slightly longer than
Theorem 1.4, but is also interesting in its own right for the following rea-
son. A hole is even if it has an even number of vertices. Computing the
maximum independent set of an even-hole-free graph in polynomial time
is a well known open question, see [9]. Hence, understanding the tree-
independence number of even-hole-free graphs would be interesting. More-
over, Theorem 1.5 implies directly the existence of even-hole-free graphs of
large tree-independence number that contain no large grids and no K₃,₄ as
induced minors. Indeed, [8] not only provides the layered wheels that we
already mentioned, but a variant, called even-hole-free layered wheels, whose
existence is stated in the next theorem.

**Theorem 1.6** (see [8]). For all integers $t \ge 1$, there exists a ($K_4$, even hole, 3PC)-free graph that contains $K_t$ as a minor.

So, the simple counter-part of the Robertson and Seymour grid theorem,
that would state that graphs with large tree-independence number should
contain a large grid or a large complete bipartite graph as an induced minor
is false, even when we restrict ourselves to even-hole-free graphs. Even-hole-
free layered wheels provide a counter-example (note that by Lemma 1.1, be-
ing $K_4$-free ensures that the high treewidth implies a high tree-independence
number).

Theorem 1.5 is best possible in some sense as we explain now. Thetas
are essential in the statement because subdivisions of $K_{3,4}$ are easily seen to
contain thetas. Also prisms are needed because of line graphs of subdivisions
of $K_{3,4}$ that contain prisms (see Fig. 2). We have to allow a path of length
zero in a prism because of the graph depicted in Fig. 6 that contains $K_{3,4}$ as
an induced minor while the only 3PC in it is a prism with a path of length
zero. Maybe pyramids are not needed in the statement, but we need them
in the proof for reasons that we now explain.

<figure><img src="image_7.png" /><figcaption>Figure 6: $K_{3,4}$ as an induced minor while all 3PC's are prisms with a path of length zero</figcaption></figure>

The proof of **Theorem 1.5** relies on a precise description of how $K_{3,3}$ can be contained as an induced minor in a 3PC-free graph, see **Lemma 5.2**. The description is too long to be stated in the introduction, but **Fig. 7** provides representations of the different possible situations.

Observe that excluding pyramids is necessary in **Lemma 5.2**, because of
the graph presented in **Fig. 8**, that contains $K_{3,3}$ as induced minor, while
the only 3PC in it is a pyramid.

Grids

Grids are easier to handle than complete bipartite graphs as shown by the
next lemma whose proof is less involved than the proofs of Theorems 1.3,
1.4 or 1.5. We do not know if a (4 × 4)-grid as an induced minor is enough
to guarantee the presence of a 3PC as an induced subgraph.

**Lemma 1.7.** If a graph *G* contains a (5 × 5)-grid as an induced minor, then *G* contains a 3PC as an induced subgraph.

Checking that layered wheels (and their even-hole-free variant) contain
no (5 × 5)-grid as an induced minor is then easy by **Theorem 1.2** and **Theorem 1.6**.

Outline of the paper

In Section 2, we prove some technical lemmas about how a connected induced subgraph of some graph *G* sees the rest of *G*. These lemmas are more or less
<figure><img src="image_8.png" /><figcaption>Figure 7: $K_{3,3}$ as an induced minor in 3PC-free graphs</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 8: $K_{3,3}$ as an induced minor in a (theta, prism)-free graph</figcaption></figure>

known already. We reprove them for the sake of completeness and because we could not find them with the precise statement that we need. Note that they are needed for all the other results. In Section 3, we prove Lemma 1.7. In Section 4, we prove Theorem 1.3. In Section 5, we prove Theorem 1.5.
We conclude the paper by Section 6 that presents several open questions.

## Notation

Let $G$ be a graph and $X$ and $Y$ be disjoint sets of vertices of $G$. We say that $X$ is *complete* to $Y$ if every vertex of $X$ is adjacent to every vertex of $Y$, $X$ is *anticomplete* to $Y$ if no vertex of $X$ is adjacent to a vertex of $Y$. We say that $X$ *sees* $Y$ if there exist $x \in X$ and $y \in Y$ such that $xy \in E(G)$. Note that the empty set is complete (and anticomplete) to every set of vertices of $G$.

By *path* we mean a sequence of vertices $p_1...p_k$ such that for all $1 \le i < j \le k$, $p_i p_j \in E(G)$ if and only if $j = i + 1$. Therefore, what we call *path* for the sake of brevity is sometimes referred to as *chordless path* or *induced path* in a more standard notation. We use the notation $aPb$ to denote the subpath of $P$ from $a$ to $b$ (possibly $a = b$ since a path may consist of a single vertex).

When we deal with a theta with two vertices of degree 3 $u$ and $v$, we say that the theta is *from u to v*. We use similar terminology for prisms and pyramids that are, respectively, from a triangle to a triangle and from a vertex to a triangle.

# 2 Types

Let $A, X, Y$ and $Z$ be four disjoint sets of vertices in a graph $G$. We distinguish three different types the set $A$ can have, see Fig. 9 for an illustration.

We say that $A$ is of *type path centered at* $Y$ with respect to $X, Y$ and $Z$ if there exists a path $P = x...z$ in $A$ such that $x$ sees $X$, $z$ sees $Z$, $P$ sees $Y$, $P \setminus x$ is anticomplete to $X$ and $P \setminus z$ is anticomplete to $Z$.

Similarly we define $A$ being of *type path centered at* $X$ and being of *type path centered at* $Z$. We say that $A$ is of *type path* with respect to $X, Y$ and $Z$ if it is of type path centered at either $X, Y$ or $Z$. Additionally, if $A$ is of type path centered at a set $W$, we call $W$ a *center for A*.

Observe that when $A$ is of type path centered at $Y$ and a unique vertex of $P$ sees $Y$, and moreover this vertex is $x$, then $A$ is also centered at $X$. In particular, if $x = z$, then $A$ is centered at $X, Y$ and $Z$.

We say that $A$ is of *type claw* with respect to $X, Y$ and $Z$ if there exists in $A$ a vertex $a$ and three paths $P = a...x$, $Q = a...y$ and $R = a...z$ such that $V(P) \cap V(Q) \cap V(R) = \{a\}$, $P \setminus a$, $Q \setminus a$ and $R \setminus a$ are pairwise anticomplete, $x$ sees $X$, $y$ sees $Y$, $z$ sees $Z$, $(P \cup Q \cup R) \setminus x$ is anticomplete
<figure><img src="image_10.png" /><figcaption>Figure 9: We illustrate the three types and a degenerate case in which type path and type claw overlap. For the three types we by way of example illustrate how $X$ is not connected to anything in $A$ but $x$. For the degenerate it is depicted that $Y$ and $Z$ are not connected to anything in $A$ but the vertex $y = z$.</figcaption></figure>

to $X$, $(P \cup Q \cup R) \setminus y$ is anticomplete to $Y$ and $(P \cup Q \cup R) \setminus z$ is anticomplete to $Z$.

Observe that possibly $a = x$, $a = y$ or $a = z$ (in fact, possibly two or three of these equalities hold). Observe that if $a = x$, then $A$ is not only of type claw, but also of type path centered at $X$, this case is additionally depicted in Fig. 9.

We say that $A$ is of *type triangle* with respect to $X$, $Y$ and $Z$ if there exists in $A$ three vertex-disjoint paths $P = x \dots x'$, $Q = y \dots y'$ and $R = z \dots z'$
such that the only edges between $P$, $Q$ and $R$ are $xy$, $yz$ and $yz$, $x'$ sees $X$, $y'$ sees $Y$, $z'$ sees $Z$, $(P \cup Q \cup R) \setminus x$ is anticomplete to $X$, $(P \cup Q \cup R) \setminus y$ is anticomplete to $Y$ and $(P \cup Q \cup R) \setminus z$ is anticomplete to $Z$.

Observe that each of $P$, $Q$ and $R$ is possibly of length 0.

**Lemma 2.1.** Let $G$ be a graph and $A, X, Y$ and $Z$ be disjoint sets of vertices of $G$. If $A$ is connected and $A$ sees $X$, $Y$ and $Z$, then $A$ is of type path, of type claw, or of type triangle with respect to $X$, $Y$ and $Z$.

*Proof.* Suppose that $A$ is not of type path. Let $P = x\dots z$ be a path in $A$ such that $x$ sees $X$, $z$ sees $Z$, $P \setminus x$ is anticomplete to $X$ and $P \setminus z$ is anticomplete to $Z$. Note that such a path exists (consider for instance a shortest path from the vertices that see $X$ to the vertices that see $Z$). Since $A$ is not of type path centered at $Y$, $P$ is anticomplete to $Y$. Let $Q = y\dots y'$ be path in $A$ disjoint from $P$ and such that $y$ sees $Y$, $y'$ sees $P$, $Q \setminus y$ is anticomplete to $Y$ and $Q \setminus y'$ is anticomplete to $P$. Note again that such a path exists (consider for instance a shortest path from the vertices that see $Y$ to the vertices that see $P$). We suppose that $P$ and $Q$ are chosen subject to the minimality of $V(P) \cup V(Q)$.

Let $a$ be the neighbor of $y'$ in $P$ closest to $x$ along $P$ and $a'$ be the neighbor of $y'$ in $P$ closest to $z$ along $P$ (note that $a = a'$ or $aa' \in E(G)$ is possible).

If $Q$ sees both $X$ and $Z$, then consider vertex $u$ in $Q$ such that $yQu$ sees both $X$ and $Z$, and choose $u$ closest to $y$ along $Q$. The path $yQu$ shows that $A$ is of type path (centered at $X$ or $Z$, possibly both, possibly also centered at $Y$ if $u = y$), a contradiction. Hence, we may assume up to symmetry that $Q$ is anticomplete to $Z$. If $Q$ sees $X$, then the path $yQy'a'Pz$ shows that $A$ is of type path centered at $X$, a contradiction. Hence, $Q$ is anticomplete to $X$ and $Z$.

If $a \neq a'$ and $aa' \notin E(G)$, then consider the path $P' = xPay'a'Pz$. If $y = y'$, then because of $P'$, $A$ is of type path centered at $Y$, a contradiction. So, $y \neq y'$ and the paths $P'$ and $Q \setminus y'$ contradict the minimality of $V(P) \cup V(Q)$.

Hence $a = a'$ or $aa' \in E(G)$. If $a = a'$, then the three paths $aPx$, $ay'Qy$ and $aPz$ show that $A$ is of type claw with respect to $X$, $Y$ and $Z$. If $aa' \in E(G)$, then the three paths $aPx$, $Q$ and $a'Pz$ show that $A$ is of type triangle with respect to $X$, $Y$ and $Z$. $\square$

The next lemma is implicitly about the presence of $K_{2,3}$ as an induced minor in a graph. In [4], it is proved along similar lines that a graph contains $K_{2,3}$ as an induced minor if and only if it contains some configuration from
a restricted list as an induced subgraph (the so-called thetas, pyramids, long prisms and broken wheels, see [4] for the definitions).

**Lemma 2.2.** Let $G$ be a 3PC-free graph and $A, B, X, Y$ and $Z$ be disjoint connected subsets of $V(G)$. If $X, Y$ and $Z$ are pairwise anticomplete, $A$ and $B$ are anticomplete to each other, and each of $A$ and $B$ sees each of $X, Y$ and $Z$, then $A$ and $B$ are of type path with respect to $X, Y$ and $Z$.

*Proof.* Suppose for a contradiction that $A$ (the argument for $B$ is the same by symmetry) is not of type path with respect to $X, Y$ and $Z$. Hence, by Lemma 2.1, $A$ we may consider the two cases below.

**Case 1:** $A$ is of type claw (and not of type path). So, there exists a vertex $a \in A$ and three paths $P = a...x$, $Q = a...y$ and $R = a...z$ like in the definition of type claw. Moreover, $a \neq x$, $a \neq y$ and $a \neq z$ for otherwise, $A$ would be of type path.

If $B$ is of type claw, then there exist a vertex $b \in B$ and three paths $P' = b...x'$, $Q' = b...y'$ and $R' = b...z'$ like in the definition of type claw. Consider a shortest path $P''$ from $x$ to $x'$ with interior in $X$, and let $Q'' = y...y'$ and $R'' = z...z'$ be defined similarly through $Y$ and $Z$. The nine paths $P, Q, R, P', Q', R', P'', Q''$ and $R''$ form a theta from $a$ to $b$, a contradiction.

If $B$ is of type triangle, a similar contradiction is found because of the existence of a pyramid in $G$.

So $B$ is not of type claw or triangle. By Lemma 2.1, $B$ is of type path, and up to symmetry we suppose that it is centered at $Y$. Let $P' = x'...z'$ be a path like in the definition of type path. Consider a shortest path $P''$ from $x$ to $x'$ with interior in $X$, and let $R'' = z...z'$ be defined similarly through $Z$. Let $Q'' = b...b'$ be a shortest path in $Y$ such that $by \in E(G)$ and $b'$ sees $P'$. Let $a'$ be the neighbor of $b'$ in $P'$ closest to $x'$ along $P'$. Let $a''$ be the neighbor of $b'$ in $P'$ closest to $z'$ along $P'$. If $a' = a''$, then $B$ is of type claw, a contradiction. If $a'a'' \in E(G)$, then the seven paths $P, Q, R, P', P'', Q''$ and $R''$ form a pyramid from $a$ to $b'a'a''$, a contradiction. Hence $a \neq a'$ and $aa' \notin E(G)$. So the paths $P, Q, R, x'P'a', a''P'z', P'', Q''$ and $R''$ form a theta from $a$ to $b'$, a contradiction.

**Case 2:** $A$ is of type triangle.

The proof is almost the same as in Case 1, so we just sketch it. If $B$ is of type claw, then $G$ contains a pyramid. If $B$ is of type triangle, then $G$ contains a prism. And if $B$ is of type path, then $G$ contains a prism or a pyramid. $\square$

Let $G$ and $H$ be two graphs. An *induced minor model* of $H$ in $G$ is a
*Proof.* If a graph contains a (5×5)-grid as an induced minor, then it contains $K_{2,3}^*$ as an induced minor, because the (5 × 5)-grid contains $K_{2,3}^*$ as an induced subgraph. The result therefore follows from **Lemma 2.3**. □

# 4 Proof of Theorem 1.3

**Lemma 4.1.** Let $G$ and $H$ be graphs and $\{X_v\}_{v \in V(H)}$ a minimal induced minor model of $H$ in $G$. For every $v \in V(H)$, the graph $G[X_v]$ does not contain cycles longer than the degree of $v$.

*Proof.* First, for every neighbor $u$ of $v$ in $H$, let us mark a single vertex in $X_v$ that is adjacent to a vertex in $X_u$. If there exists a connected induced proper subgraph of $G[X_v]$ that contains all of the marked vertices, we contradict the minimality of the induced minor model.

Suppose that $G[X_v]$ contains a cycle of length longer than the degree of $v$, and let $C \subseteq X_v$ be the vertices of this cycle. We say that a vertex $w \in C$ is *necessary* if either $w$ is marked or there exists a connected component $Y$ of $G[X_v \setminus C]$ that contains a marked vertex and whose only neighbor in $C$ is the vertex $w$. Because $|C|$ is larger than the number of marked vertices, there exists a vertex in $C$ that is not necessary, let $w \in C$ be such a vertex. We remove from $X_v$ the vertex $w$ and every component of $G[X_v \setminus C]$ whose only neighbor in $C$ is $w$. All of the remaining vertices in $X_v$ are still connected to $C \setminus \{w\}$ and contain all of the marked vertices, so we get a connected induced proper subgraph of $G[X_v]$ that contains all of the marked vertices, which is a contradiction. □

**Lemma 4.1** is useful for asserting that $G[X_v]$ is a tree, which in turn is useful for obtaining degree-1 vertices in $G[X_v]$. We make use of degree-1 vertices with the following lemma.

**Lemma 4.2.** Let $\{X_v\}_{v \in V(H)}$ be a minimal induced minor model of a graph $H$ in a graph $G$, and let $v \in V(H)$. For every vertex $w \in X_v$ whose degree is one in $G[X_v]$, there exists $u \in V(H) \setminus \{v\}$ so that $w$ is the only neighbor of $X_u$ in $X_v$.

*Proof.* Otherwise, we could remove $w$ from $X_v$ and contradict the minimality of $\{X_v\}_{v \in V(H)}$. □

We say that such a branch set $X_u$ is *private* to the vertex $w$. We may now prove **Theorem 1.3** which we restate below.
**Theorem 1.3.** If a graph $G$ contains $K_{134,12}$ as an induced minor, then $G$ contains a cycle of length at most 12 or a theta as an induced subgraph.

*Proof.* Let $p = 12$ and $t = 2\binom{p}{2} + 2 = 134$. Let $G$ be a graph with girth at least $p+1$, and let $\{X_v\}_{v \in V(K_{t,p})}$ be a minimal induced minor model of $K_{t,p}$ in $G$. We denote the branch sets corresponding to vertices of $K_{t,p}$ on the side with $t$ vertices by $A_1, \dots, A_t$ and on the other side by $B_1, \dots, B_p$. Note that $G$ is triangle-free.

First suppose that there are two branch sets $A_i$, $A_j$ of size $|A_i|, |A_j| \le 2$. In this case, there must be a vertex $v \in A_i$ that is adjacent to at least $p/2$ different branch sets on the other side, and a vertex $u \in A_j$ that is adjacent to at least $p/4 = 3$ different branch sets on the other side that $v$ is also adjacent to. Fix three different branch sets $B_a, B_b, B_c$ that both $v$ and $u$ are adjacent to. Now, by selecting in each branch set $B_a, B_b, B_c$ a shortest path from a neighbor of $v$ to a neighbor of $u$, we obtain a theta from $u$ to $v$.

We may therefore assume that at least $t-1$ of the branch sets $A_1, \dots, A_t$ contain at least three vertices. By Lemma 4.1 and because $G$ has girth at least $p+1$, for all branch sets $A_1, \dots, A_t$ the induced subgraph $G[A_i]$ is a tree, and for all such sets with $|A_i| \ge 3$, the tree must have two non-adjacent leaves $v$ and $u$. By Lemma 4.2, both $v$ and $u$ have a private branch set on the other side, so we can label each branch set $A_i$ with $|A_i| \ge 3$ with an unordered pair $\{B_j, B_k\}$ so that $B_j$ is private to $v$ and $B_k$ is private to $u$.

Now, because $t-1 = 2\binom{p}{2} + 1$, there must exist three branch sets $A_a, A_b$, and $A_c$ that are labeled with the same pair $\{B_j, B_k\}$. By contracting both $B_j$ and $B_k$ into a single vertex and taking the paths in $A_a, A_b$, and $A_c$ between the corresponding leaves, we obtain $K_{2,3}^*$ as an induced minor. By Lemma 2.3, $G$ must contain a theta since the theta is the only triangle-free 3PC. $\square$

# 5 Proof of Theorem 1.5

We start with an improvement of Lemma 2.2.

**Lemma 5.1.** Let $G$ be a 3PC-free graph and $k \ge 2$ be an integer. Suppose that $X, Y, Z$ and $A_1, \dots, A_k$ are disjoint connected subsets of $V(G)$, $X$, $Y$ and $Z$ are pairwise anticomplete, $A_1, \dots, A_k$ are pairwise anticomplete, and for every $i \in \{1, \dots, k\}$, $A_i$ sees $X, Y$ and $Z$.

Then the $A_i$'s are all of type path with respect to $X, Y$ and $Z$ and furthermore, one of $X, Y$ and $Z$ is a center for all of them.
*Proof.* By Lemma 2.2 applied to $A = A_i$, $B = A_j$ for some $j \neq i$ and $X, Y$ and $Z$, we see that all $A_i$'s are of type path with respect to $X, Y$ and $Z$. It remains to prove that they all share a common center.

We denote by $\tau(A_i)$ the sets of all elements $U \in \{X, Y, Z\}$ such that $A_i$ is centered at $U$. Note that for all $i \in \{1, \dots, k\}$, $\tau(A_i)$ is nonempty. It is enough to prove that for all $i, j \in \{1, \dots, k\}$, either $\tau(A_i) \subseteq \tau(A_j)$ or $\tau(A_j) \subseteq \tau(A_i)$. Indeed, this implies that the sets $\tau(A_i)$ are linearly ordered by the inclusion, so that $\cap_{i \in \{1, \dots, k\}} \tau(A_i)$ is non-empty and contains the common center that we are looking for.

So suppose for a contradiction that $A = A_i$ and $B = A_j$ are such that $\tau(A_i)$ and $\tau(A_j)$ are inclusion-wise incomparable. So, up to symmetry, $A$ is centered at $X$ and not at $Y$ while $B$ is centered at $Y$ and not at $X$.

Since $A$ is centered at $X$, there exists $P = u \dots u'$ in $A$ such that $u$ sees $Y$, $u'$ sees $Z$, $P$ sees $X$, $P \setminus u$ is anticomplete to $Y$ and $P \setminus u'$ is anticomplete to $Z$. Since $B$ is centered at $Y$, there exists $Q = v \dots v'$ in $B$ such that $v$ sees $X$, $v'$ sees $Z$, $Q$ sees $Y$, $Q \setminus v$ is anticomplete to $X$ and $Q \setminus v'$ is anticomplete to $Z$.

Let $R = z \dots z'$ be a shortest path in $Z$ such that $u'z \in E(G)$ and $z'v' \in E(G)$. Let $S = y \dots y'$ be a shortest path in $Y$ such that $y$ sees $Q$ and $y'u \in E(G)$. Let $T = x \dots x'$ be a shortest path in $X$ such that $x$ sees $P$ and $x'v \in E(G)$. Observe that each of $P, Q, R, S$ and $T$ can be of length 0.

Let $a$ be the neighbor of $x$ in $P$ closest to $u$ along $P$. Let $a'$ be the neighbor of $x$ in $P$ closest to $u'$ along $P$. Let $b$ be the neighbor of $y$ in $Q$ closest to $v$ along $Q$. Let $b'$ be the neighbor of $y$ in $Q$ closest to $v'$ along $Q$. See Figure 10.

Suppose first that $a = a'$. Observe that $a = a' \neq u$ for otherwise $A$ would be centered at $Y$, contrary to our assumption. Hence, $ay \notin E(G)$. If $b = b'$, then $P, Q, R, S$ and $T$ form a theta from $a$ to $b$, so $b \neq b'$. If $bb' \in E(G)$, then $P, Q, R, S$ and $T$ form a pyramid from $a$ to $ybb'$. If $bb' \notin E(G)$, then $P, vQb, b'Qv', R, S$ and $T$ form a theta from $a$ to $y$ (because $ay \notin E(G)$ as already noted). Hence $a \neq a'$, and symmetrically we can prove that $b \neq b'$.

Suppose now $aa' \in E(G)$. If $bb' \in E(G)$, then $P, Q, R, S$ and $T$ form a prism from $xa'a$ to $ybb'$. If $bb' \notin E(G)$, then $P, vQb, b'Qv', R, S$ and $T$ form a pyramid from $y$ to $xa'a'$. Hence $aa' \notin E(G)$, and symmetrically we can prove that $bb' \notin E(G)$.

We are left with the case where $a \neq a'$, $aa' \notin E(G)$, $b \neq b'$ and $bb' \notin E(G)$. Then $uPa, a'Pu', vQb, b'Qv', R, S$ and $T$ form a theta from $x$ to $y$. $\square$

The following lemma describes what happens when $K_{3,3}$ is an induced
<figure><img src="image_11.png" /><figcaption>Figure 10: Paths $P, Q, R, S$ and $T$ in the proof of Lemma 5.1</figcaption></figure>

minor of some 3PC-free graph. It is worth noting that it has a true converse that we do not need to state formally. More precisely, if in any graph six paths $A, B, C, P, Q$ and $R$ satisfy all the properties described in Lemma 5.2, then they form a model for a $K_{3,3}$ induced minor, and moreover the graph that they induce can be checked to be 3PC-free, see Fig. 7.

Note that the statement of Lemma 5.2 is not completely symmetric. Namely, $A, B$ and $C$ are assumed to be minimal while $X, Y$ and $Z$ are not. This yields a slightly stronger statement which is needed for the application in the proof of Theorem 1.5.

**Lemma 5.2.** Let $G$ be a 3PC-free graph and $A, B, C, X, Y$ and $Z$ be connected disjoint subsets of $V(G)$ such that $X, Y$ and $Z$ are pairwise anticomplete, $A, B$ and $C$ are pairwise anticomplete and each of $A, B$ and $C$ sees each of $X, Y$ and $Z$. Suppose that no connected proper subset of $A$ (resp. $B$ and $C$) sees each of $X, Y$ and $Z$. Then, there exist six vertex-disjoint paths $A' = a...a', B' = b...b', C' = c...c', P = p...p', Q = q...q'$ and $R = r...r'$ in $G$ such that:

* Each of $A', B'$ and $C'$ is equal to exactly one of $A, B$ or $C$.

* Each of $X, Y$ and $Z$ contains exactly one of $P, Q$ or $R$.

* $H = aA'a'rRr'c'C'cp'Ppa$ is a hole.
• $B' \setminus b$ (resp. $B' \setminus b'$, $Q \setminus q$, $Q \setminus q'$) is anticomplete to $P$ (resp. $R, A', C'$).

• $B'$ and $Q$ both have length at most 1 (so they each contain at most two vertices).

• Each of $P$, $R$, $A'$ and $C'$ contains at least three vertices and $b$ (resp. $b'$, $q$, $q'$) has at least two neighbors in $P$ (resp. $R$, $A'$, $C'$).

• $B'$ is complete to $Q$, or $G[B' \cup Q]$ has four vertices and five edges.

*Proof.* By Lemma 5.1, $A, B$ and $C$ are of type path with respect to $X, Y$ and $Z$, centered at some $Y' \in \{X, Y, Z\}$. By Lemma 5.1, $X, Y$ and $Z$ are of type path with respect to $A, B$ and $C$, centered at some $B' \in \{A, B, C\}$. We let $X', Z'$, $A'$ and $C'$ be such that $\{A', B', C'\} = \{A, B, C\}$ and $\{X', Y', Z'\} = \{X, Y, Z\}$.

So, $A'$ contains some path that sees $X'$, $Y'$ and $Z'$ as in the definition of type path centered at $Y'$, but by the assumption about the minimality of $A, B$ or $C$, we see that this path is in fact $A'$ itself. So $A'$ is equal to exactly one of $A, B$ or $C$. The arguments work also with $B$ and $C$, so that $A' = a \dots a'$, $B' = b \dots b'$, $C' = c \dots c'$, each of $a, b$ and $c$ sees $X'$, each of $a'$, $b'$ and $c'$ sees $Z'$, each of $A'$, $B'$ and $C'$ sees $Y'$, each of $A' \setminus a$, $B' \setminus b$ and $C' \setminus c$ is anticomplete to $X'$ and each of $A' \setminus a'$, $B' \setminus b'$ is and $C' \setminus c'$ is anticomplete to $Z'$.

Also $X'$ contains a path $P = p \dots p'$ such that $p$ sees $A'$, $p'$ sees $C'$, $P \setminus p$ is anticomplete to $A'$, $P \setminus p'$ is anticomplete to $C'$ and $P$ sees $B'$. Note that we cannot claim that $X' = P$, since we made no assumption about the minimality of $X$. But since $A' \setminus a$ is anticomplete to $X'$ and $P \setminus p$ is anticomplete to $A'$, the only possible edge between $P$ and $A'$ is $pa$. Similarly, $p'c$ is the only edge between $P$ and $C'$. Moreover, $P$ sees $B'$, and since $B \setminus b$ is anticomplete to $X'$, we know that $b$ sees $P$ (and not only $X'$).

Similarly, $Z'$ contains a path $R = r \dots r'$ with $ra' \in E(G)$, $r'c' \in E(G)$, $R \setminus r$ is anticomplete to $A'$, $R \setminus r'$ is anticomplete to $C'$ and such that $b'$ sees $R$. Observe that $A'$, $P$, $C'$ and $R$ form a hole $H$.

Also $Y'$ is of type path with respect to $A, B$ and $C$ and centered at $B'$. So, $Y'$ contains a path $Q = q \dots q'$ such that $q$ sees $A'$, $q'$ sees $C'$, $Q \setminus q$ is anticomplete to $A'$, $Q \setminus q'$ is anticomplete to $C'$ and $Q$ sees $B'$.

Let $\alpha$ be the neighbor of $q$ in $A'$ closest to $a$ along $A'$. Let $\alpha'$ be the neighbor of $q$ in $A'$ closest to $a'$ along $A$. Let $\beta$ be the neighbor of $b$ in $P$ closest to $p$ along $P$. Let $\beta'$ be the neighbor of $b$ in $P$ closest to $p'$ along $P$. Let $\gamma$ be the neighbor of $q'$ in $C'$ closest to $c$ along $C'$. Let $\gamma'$ be the
neighbor of $q'$ in $C'$ closest to $c'$ along $C'$. Let $\delta$ be the neighbor of $b'$ in $R$
closest to $r$ along $R$. Let $\delta'$ be the neighbor of $b'$ in $R$ closest to $r'$ along $R$.
See Fig. 11.

<figure><img src="image_12.png" /><figcaption>Figure 11: Paths $A', B', C', P, Q$ and $R$ in the proof of Lemma 5.2</figcaption></figure>

Suppose that $B'$ has length at least 2. Then $B$ and $H$ contain a theta,
a prism or a pyramid, namely from $\beta$ (if $\beta = \beta'$) or $b\beta\beta'$ (if $\beta\beta' \in E(G)$)
or $b$ (otherwise), to $\delta$ (if $\delta = \delta'$) or $b'\delta\delta'$ (if $\delta\delta' \in E(G)$) or $b'$ (otherwise).
Hence $B'$ has length at most 1, meaning that either $b = b'$ or $bb' \in E(G)$.
Similarly, $Q$ has length at most 1 and $q = q'$ or $qq' \in E(G)$.

Suppose that $\beta = \beta'$. Then $b = b'$ for otherwise $B$ and $H$ contain a
theta (if $\delta = \delta'$), or a pyramid from $\beta$ to $b'\delta\delta'$ (if $\delta\delta' \in E(G)$), or a theta
from $\beta$ to $b'$ (otherwise). Since $B'$ sees $Q$, $b$ has a neighbor in $Q$. If $b$ has a
unique neighbor in $Q$, say $q$ up to symmetry (so either $q = q'$, or $q \neq q'$ and
$bq' \notin E(G)$), then the three paths $\beta bq$, $\beta P p a A' \alpha q$ and $\beta P p' c C' \gamma q' q$
form a theta from $\beta$ to $q$. So, $b$ has two neighbors in $Q$. Hence, the three paths $\beta b$,
$\beta P p a A' \alpha q$ and $\beta P p' c C' \gamma q'$ form a pyramid from $\beta$ to $bqq'$. We proved that
$\beta \neq \beta'$.

Suppose that $\beta\beta' \in E(G)$. Then $b = b'$ as otherwise $B$ and $H$ contains a
pyramid from $\delta$ to $b\beta\beta'$ (if $\delta = \delta'$), a prism from $b\beta\beta'$ to $b'\delta\delta'$ (if $\delta\delta' \in E(G)$)
or a pyramid from $b'$ to $b\beta\beta'$ (otherwise). Since $B'$ sees $Q$, $b$ has a neighbor
in $Q$. If $b$ has a unique neighbor in $Q$, say $q$ up to symmetry (so either
$q = q'$, or $q \neq q'$ and $bq' \notin E(G)$), then the three paths $qb$, $q\alpha A' a p P \beta$ and
$qq'\gamma C'cp'P\beta'$ form a pyramid from $q$ to $b\beta\beta'$. So, $b$ has two neighbors in $Q$. Hence, the three paths $b, q\alpha A'apP\beta$ and $q'\gamma C'cp'P\beta'$ form a prism from $bqq'$ to $b\beta\beta'$. We proved that $\beta\beta' \notin E(G)$. This implies that $P$ contains at least three vertices and $b$ has at least two neighbors in $P$.

By a symmetric argument, we can prove that $R$ (resp. $A'$, $C'$) contains at least three vertices and $b'$ (resp. $q$, $q'$) has at least two neighbors in it. It remains to prove that $B'$ is complete to $Q$, or $B' \cup Q$ induces a graph with four vertices and five edges. So suppose that $B'$ is not complete to $Q$.

Since $B'$ sees $Q$ and $B'$ is not complete to $Q$, there is at least one edge and at least one non-edge with ends in $B$ and $Q$. So, there must be a vertex, either in $B$ or $Q$, that is incident to such an edge and such a non-edge. Up to symmetry, we assume that this vertex is $b$ and $bq \in E(G)$ (so $bq' \notin E(G)$ and $q \neq q'$). If $b = b'$, or if $b \neq b'$ and $G[B' \cup Q]$ has only three edges (namely $bb'$, $qq'$ and $bq$), then $bqq'$, $b\beta'Pp'cC'\gamma q'$ and $bb'\delta'Rr'c'C'\gamma'q'$ form a theta from $b$ to $q'$. We proved that $b \neq b'$ and $G[B' \cup Q]$ has at least four edges. So, $G[B' \cup Q]$ has four vertices and it remains to prove that it has exactly five edges. So suppose for a contradiction that $G[B' \cup Q]$ has exactly four edges.

If $b'q' \in E(G)$ (and therefore $b'q \notin E(G)$), then $bqq'$, $bb'q'$ and $b\beta'Pp'cC'\gamma q'$ form a theta from $b$ to $q'$. If $b'q \in E(G)$ (and therefore $b'q' \notin E(G)$), then $q'q$, $q'\gamma C'cp'P\beta'b$ and $q'\gamma'C'c'r'R\delta'b'$ form a pyramid from $q'$ to $bb'q$. $\square$

**Lemma 5.3.** Let $G$ be a 3PC-free graph and $A, B, C, X, Y$ and $Z$ be connected disjoint subsets of $V(G)$ such that $X, Y$ and $Z$ are pairwise anticomplete, $A, B$ and $C$ are pairwise anticomplete, and each of $A, B$ and $C$ sees each of $X, Y$ and $Z$. Suppose that no connected proper subset of $A$ (resp. $B$ and $C$) sees each of $X, Y$ and $Z$. Then exactly one of $A, B$ and $C$ contains at most 2 vertices.

*Proof.* Follows directly from Lemma 5.2. $\square$

We may now prove Theorem 1.5 that we restate.

**Theorem 1.5.** If a graph $G$ contains $K_{3,4}$ as an induced minor, then $G$ contains a 3PC as an induced subgraph.

*Proof.* Suppose for a contradiction that a 3PC-free graph $G$ contains $K_{3,4}$ has an induced minor. So, $G$ contains seven disjoint connected sets $X, Y, Z, A, B, C$ and $D$ such that $X, Y$ and $Z$ are pairwise anticomplete, $A, B, C$ and $D$ are pairwise anticomplete, and each of $X, Y$ and $Z$ sees each of $A, B, C$ and $D$. We suppose that these sets are chosen subject to the
minimality of $A \cup B \cup C \cup D$. It follows that no proper connected subset of $A$ (resp. $B, C, D$) sees $X, Y$ and $Z$ (note that it is important here that no assumption is made about the minimality of $X, Y$ and $Z$).

By Lemma 5.3 applied to $A, B, C, X, Y$ and $Z$, exactly one of $A, B$ and $C$ has size at most 2, say $|A| \le 2$, $|B| > 2$ and $|C| > 2$. Hence, by Lemma 5.3 applied to $B, C, D, X, Y$ and $Z$, we have $|D| \le 2$. Hence, $A, B, D, X, Y$ and $Z$ contradict Lemma 5.3. □

# 6 Open questions

We need pyramids in Theorem 1.5 only for the sake of the precise description of Lemma 5.2, see Fig. 8. We therefore wonder whether pyramids in Theorem 1.5 are really needed. More precisely, we do not know whether a (theta, prism)-free graph that contains $K_{3,4}$ as an induced minor exists.

A wheel is a graph made of a hole called the rim together with a vertex called the center that has at least three neighbors on the rim. It is even if the center has an even number of neighbors in the rim. It is well known (and easy to check) that even-hole-free graphs contain no prisms, no thetas and no even wheels as induced subgraphs, since each of these configurations implies the presence of an even hole. Conversely, many theorems about even-hole-free graphs suggest that (theta, prism, even wheel)-free graphs, that are called odd signable graphs, capture the essentials structural properties of even-hole-free graphs, see [9, 10]. We believe that the following is true.

**Conjecture 6.1.** If $G$ is an odd signable graph (in particular if $G$ is an even-hole-free graph), then $G$ does not contain $K_{3,3}$ as an induced minor.

Observe that we do not know whether the even-hole-free layered wheels contain $K_{3,3}$ as an induced minor. A proof of Conjecture 6.1 would imply that they do not. We also propose the following.

**Conjecture 6.2.** If $G$ contains $K_6$ as a minor, then $G$ contains a triangle (as a subgraph) or $G$ contains $K_{3,3}$ as an induced minor.

In [1], it is proved that triangle-free odd-signable graphs (in particular (triangle, even-hole)-free graphs) have treewidth at most 5 and therefore do not contain $K_6$ as a minor. So, provided that Conjecture 6.1 is true, Conjecture 6.2 is just a more precise statement.

Here are some remarks about Conjecture 6.2. It is false with a $K_5$ assumption instead of a $K_6$ assumption, see Fig. 12 where an (even hole, triangle)-free graph with a $K_5$ minor, first discovered in [2], is represented.
It is false with a "$K_{3,4}$ as an induced minor or triangle" conclusion because of the layered wheels. Provided that Conjecture 6.1 is true, it is false with a "$K_{3,3}$ as an induced minor or 3PC as an induced subgraph" conclusion, or with a "$K_{3,3}$ as an induced minor or $K_4$ as subgraph" conclusion, because of the even-hole-free layered wheels that are pyramid-free and $K_4$-free by Theorem 1.6. Conjecture 6.2 would therefore provide a statement that is best possible in many ways.

<figure><img src="image_13.png" /><figcaption>Figure 12: A $K_5$ minor in an (even hole, triangle)-free graph. To see even hole-freeness first note that no even hole can contain a fat red edge.</figcaption></figure>

It might be interesting to study the implications of a $K_{3,3}-e$ induced minor in an even-hole free graph, where $K_{3,3}-e$ is the graph obtained from $K_{3,3}$ by removing one edge. In Fig. 13, an even-hole-free graph that contains $K_{3,3}-e$ as an induced minor is represented, and we observe that this graph plays an important role in the structural study of even-hole-free graphs, see [9]. In Fig. 14, another example of a graph that contains $K_{3,3}-e$ as an induced minor is represented, and we observe that this graph contains an even wheel.

More generally, we believe that studying implications between different containment relations for different kinds of graphs might have more applications. For instance, this approach is used in [4] to design a polynomial time algorithm that decides whether an input graph contains $K_{2,3}$ as an induced minor. We wonder what is the complexity of detecting $K_{3,3}$ as an induced minor.
<figure><img src="image_14.png" /><figcaption>Figure 13: A $K_{3,3} - e$ induced minor in an (even hole, triangle)-free graph</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Figure 14: A $K_{3,3}-e$ induced minor in a graph without triangles and withoutthetaas</figcaption></figure>

7 Acknowledgement

We are grateful to Marthe Bonamy, Sepehr Hajebi, Martin Milanič, Sophie
Spirkl and Kristina Vušković for helpful discussions.

Maria Chudnovsky is supported by NSF-EPSRC Grant DMS-2120644 and by AFOSR grant FA9550-22-1-0083.

Meike Hatzel is supported by the Federal Ministry of Education and Research (BMBF) and by a fellowship within the IFI programme of the German Academic Exchange Service (DAAD) and by the Institute for Basic
Science (IBS-R029-C1).

Tuukka Korhonen is supported by the Research Council of Norway via the project BWCA (grant no. 314528).

Nicolas Trotignon is partially supported by the French National Research Agency under research grant ANR DIGRAPHS ANR-19-CE48-0013-01 and the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program Investissements d'Avenir (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).

Part of this research was conducted during two Graph Theory Workshops at the McGill University Bellairs Research Institute, and we express our gratitude to the institute and to the organizers of the workshop.

Part of this work was done when Nicolas Trotignon visited Maria Chudnovsky at Princeton University with generous support of the H2020-MSCA-RISE project CoSP- GA No. 823748.

## References

[1] Kathie Cameron, Murilo V. G. da Silva, Shenwei Huang, and Kristina Vušković. Structure and algorithms for (cap, even hole)-free graphs. *Discrete Mathematics*, 341(2):463–473, 2018.

[2] Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, and Kristina Vušković. Triangle-free graphs that are signable without even holes. *Journal of Graph Theory*, 34(3):204–220, 2000.

[3] Clément Dallard, Martin Milanič, and Kenny Storgel. Treewidth versus clique number. II. Tree-independence number. *Journal of Combinatorial Theory, Series B*, 164:404–442, 2024.

[4] Clément Dallard, Maël Dumas, Claire Hilaire, Martin Milanič, Anthony Perez, and Nicolas Trotignon. Detecting $k_{2,3}$ as an induced minor. In Adele Anna Rescigno and Ugo Vaccaro, editors, *Combinatorial Algorithms - 35th International Workshop, IWOCA 2024, Ischia, Italy, July 1-3, 2024, Proceedings*, volume 14764 of Lecture Notes in Computer Science, pages 151–164. Springer, 2024. arXiv:2402.08332, 2024.

[5] Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanič. Computing tree decompositions with small independence number. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, *51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, 2024*.
*Estonia*, volume 297 of *LIPIcs*, pages 51:1–51:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.

[6] Paloma T. Lima, Martin Milanič, Peter Mursic, Karolina Okrasa, Pawel Rzazewski, and Kenny Storgel. Tree decompositions meet induced matchings: Beyond max weight independent set. In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors, *32nd Annual European Symposium on Algorithms, ESA 2024, September 2-4, 2024, Royal Holloway, London, United Kingdom*, volume 308 of *LIPIcs*, pages 85:1–85:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.

[7] Neil Robertson and Paul Seymour. Graph minors. V. Excluding a planar graph. *Journal of Combinatorial Theory, Series B*, 41(1):92–114, 1986.

[8] Ni Luh Dewi Sintiari and Nicolas Trotignon. (Theta, triangle)-free and (even hole, $K_4$)-free graphs - Part 1: Layered wheels. *Journal of Graph Theory*, 97(4):475–509, 2021.

[9] Kristina Vušković. Even-hole-free graphs: a survey. *Applicable Analysis and Discrete Mathematics*, 10(2):219–240, 2010.

[10] Kristina Vušković. The world of hereditary graph classes viewed through Truemper configurations. In S. Gerke S.R. Blackburn and M. Wildon, editors, *Surveys in Combinatorics, London Mathematical Society Lecture Note Series*, volume 409, pages 265–325. Cambridge University Press, 2013.

[11] Nikola Yolov. Minor-matching hypertree width. In *Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018*, pages 219–233. SIAM, 2018.