17 problems

Sintiari–Trotignon conjecture. For every $t$ there exists a constant $c_t$ such that every $n$-vertex $K_t$-free and even-hole-free graph has treewidth at most

Let $G$ be a graph with no induced cycle of even length at least $4$. A vertex is bisimplicial if its neighbor set is the union of two cliques. Reed's conjecture. Every even hole-f…

For a positive integer $t$, an (even hole, $K_t$)-free graph is a graph containing neither an even hole nor a clique $K_t$ as an induced subgraph. Logarithmic treewidth conjecture.…

A hole is an induced cycle of length at least four, and a graph is even-hole-free if it has no hole of even length. For a graph $G$, let $\chi(G)$ denote its chromatic number and…

Let $G$ be an even-hole-free graph, meaning that $G$ has no induced cycle of even length at least four. Write $\chi(G)$ for its chromatic number and $\omega(G)$ for its clique numb…

Even-hole-free 3-divisibility conjecture. Every even-hole-free graph is 3-divisible.

Even-hole-free conjecture. Every even-hole-free graph is perfectly divisible.

Odd signable graph conjecture. 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.

Let $\operatorname{tw}(G)$ denote the treewidth of $G$. The sparse induced-subgraph conjecture for even-hole-free graphs. For every integer $t\geq 1$, every even-hole-free graph of…

Let $t\geq 4$ be an integer, let $H$ be a $2$-forest, and let an $(\mathcal{F})$-free graph mean a graph with no induced subgraph isomorphic to a member of $\mathcal{F}$. The bound…

For an integer $k\geq 1$, a $k$-forest is a $K_{k+2}$-free chordal graph; in particular, a $2$-forest is a $K_4$-free chordal graph. An even-hole-free graph has no induced cycle of…

Let $t\geq 4$ be an integer, let $H$ be a graph, and call $H$ $K_4$-free chordal if it is chordal and contains no induced subgraph isomorphic to $K_4$. An even-hole-free graph has…

Sintiari and Trotignon's conjecture. Every (even-hole, $K_4$)-free graph of sufficiently large treewidth contains a diamond as an induced subgraph.

For a graph $G=(V(G),E(G))$, let $\operatorname{tw}(G)$ denote its treewidth, defined as the minimum width of a tree decomposition, where the width is the maximum bag size minus on…

For a graph $G=(V(G),E(G))$, a tree decomposition $(T,\chi)$ consists of a tree $T$ and a map $\chi:V(T)\to 2^{V(G)}$ satisfying the usual vertex coverage, edge coverage, and conne…

Let $G$ be a graph. A hole is an induced cycle of length at least four, and an even hole is a hole with an even number of vertices. The maximum degree of $G$ is denoted by…

Let $G$ be an even-hole-free graph, meaning that $G$ has no induced cycle of even length, and let the maximum degree of $G$ be at most $\delta$. The treewidth of $G$, denoted by…