14 problems

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.

For a graph $G$, let $\operatorname{tw}(G)$ denote its treewidth. A graph is even-hole-free if it has no induced cycle of even length at least four, and the diamond is the graph on…

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…

An (even hole, diamond)-free graph is a graph containing neither an even hole nor a diamond as an induced subgraph. Its tree independence number is denoted by…