16 problems

Let $T$ be a forest, and let a graph be $T$-free if it has no induced subgraph isomorphic to $T$. A hereditary graph class is chi-bounded if there is a function…

Let $\mathcal{G}$ be a hereditary class of graphs. A class has bounded tree-independence number if there is a constant $c\in\mathbb{N}$ such that every graph in the class admits a…

Let $F$ be a linear forest, meaning a forest whose connected components are paths. Let $\widehat{(K_4,-)}$ be the specified signed complete graph, and call a finite set of signed g…

Let $\mathcal{G}$ be a hereditary graph class. A graph $H$ is $H$-free in $\mathcal{G}$ when graphs in the relevant subclass have no induced subgraph isomorphic to $H$. The class…

Let $\mathcal{G}$ be a hereditary graph class. A graph is $2$-degenerate if every induced subgraph has a vertex of degree at most $2$, and $\mathcal{G}$ is…

Gartland–Lokastov's conjecture. For every planar graph $H$, there exists $k\in\mathbb{N}$ such that every $H$-induced-minor-free graph $G$ admits a $(k,1)$-balanced separator.

Let $\mathcal{G}$ be a hereditary graph class. It is $(\operatorname{tw},\operatorname{had})$-bounded if there is a function $f$ such that…

Let $H$ be a graph. A prime graph is one admitting no non-trivial decomposition with respect to the direct product, a core is a graph with no homomorphism onto a proper subgraph, a…

Let $q\geq 3$ be odd, let $p\geq 1$, and let $G_{q,p}$ be the graph constructed in the paper. Here, $P_t$ denotes the path on $t$ vertices, and a graph is $P_t$-free if it has no i…

Stable hereditary graph class characterization conjecture. The following properties are equivalent:

Let $\mathcal T$ denote the graph class of twisted cycles in a chain, namely the class represented by the constructions discussed around Figure. A graph class is minimal of unbound…

Let $\mathcal X$ be a graph class with bounded $\lambda$ and unbounded lettericity, and let $\mathcal C_k$ denote the chains-in-a-cycle classes defined earlier in the paper. Chains…

A graph class is minimal of unbounded $\lambda$ if it has unbounded $\lambda$, while every proper hereditary subclass has bounded $\lambda$. Minimal-class conjecture for $\lambda$.…

Minimal-class conjecture for shrub-depth and rank-depth. Shrub-depth and rank-depth are unbounded in $\mathcal X$ if and only if $\mathcal X$ contains a minimal hereditary class of…

Erdős–Hajnal conjecture. There are constants $A$ and $k$ such that

Let $X$ be a minimal hereditary class of graphs of unbounded clique-width. A canonical infinite coloured antichain is the canonical infinite coloured antichain associated with such…