28 problems

Let ${\mathcal C}$ be a hereditary graph class, and suppose that ${\mathcal C}$ is chi-bounded, meaning that its chromatic number is bounded by a function of its clique number. Esp…

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…

Implicit Graph Conjecture. Every such class ${\mathcal F}$ admits an adjacency labeling scheme with labels of size $O(\log n)$.

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…

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…

Let $\mathcal{S}$ be the class of forests in which every connected component is a tree with at most three leaves; its members are called tripods. A hereditary class is finitely-def…

Let $F$ be a linear forest, let $\widetilde{K}_2$ be the signed graph obtained from $K_2$ by replacing its edge with a digon, and let a finite set of signed graphs be a GS set when…

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…

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…

Let $\mathscr{F}$ denote the class of thick forests. An infinite family of forbidden subgraphs for $\mathscr{F}$ is a family of graphs containing arbitrarily large members, each ex…

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

Let $\mu$ be a periodic nonconstant $0$-$1$ word, and let $G_{\mu}$ be the graph associated with $\mu$. A bound of a hereditary class of finite structures is a structure not in the…

Stable hereditary-class adjacency sketch conjecture. The class ${\mathcal F}$ admits a constant-size adjacency sketch.

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$.…

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

Let an infinite word over the alphabet $\{0,1,2\}$ define a hereditary bipartite graph class by taking the finite induced subgraphs of the associated infinite graph whose vertices…

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…

Let ${\cal F}$ be a hereditary class of graphs. A $k$-creature consists of four pairwise disjoint vertex sets $A$, $B$, $X=\{x_1,\ldots,x_k\}$, and $Y=\{y_1,\ldots,y_k\}$ such that…

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