21 problems

Flip-width subpolynomial collapse conjecture. The following conditions are equivalent:

Let $\mathcal{F}$ be a finite class of graphs, and let $\mathcal{F}$-free mean having no induced subgraph isomorphic to a member of $\mathcal{F}$. A multiclaw is a graph each compo…

Let $G$ be a $5$-connected non-planar graph with at least seven vertices. Kawarabayashi–Maharry conjecture. The graph $G$ contains both a $K_{3,4}$ minor and a $K_6^-$ minor. The s…

Let $\mathscr C$ be a class of TOWS graphs, and let $\mathsf{Sp}(\mathscr C)$ be the class obtained by the paper's sparsifying transduction. Let $\Pi_S$ be a downset of weakly spar…

Gartland–Lokshtanov's conjecture. For every planar graph $H$ there exists an integer $k_H$ such that every $H$-induced-minor-free graph $G$ has a balanced separator dominated by at…

Let $G$ be a graph and let ${\cal P}$ be a monotone partition of $V(G)$ into cliques. Assume that the box graph $b(G;{\cal P})$ is a chordless cycle. The logarithmic cyclic-box con…

Let $G$ be a graph, and let ${\cal P}=(A_1,\ldots,A_k)$ be a monotone partition of $V(G)$ into cliques. The box graph $b(G;{\cal P})$ has a chordless cycle…

4-candidate generation conjecture. Every bichromatic-forbidding 4-candidate can be obtained from the diamond by a sequence of the operations described in Lemmas 10ext, extproj, and…

Let $G$ be a finite simple undirected graph. For each vertex $v\in V(G)$, let $G_v=[G-v]_{\cong}$ be its card, and let … be its deck. The graph $G$ is reconstructible if every grap…

Surface transduction-order conjecture. Let $\Sigma$ and $\Gamma$ be surfaces such that $\Sigma\not\preccurlyeq\Gamma$. Then

Gajarsky–Pilipczuk–Toruńczyk's cliquewidth obstruction conjecture. A class of graphs $\mathscr{C}$ has unbounded cliquewidth if and only if $\mathscr{C}$ transduces a class…

Let $H$ be a graph which is a disjoint union of triangles and paths of length at most $12$, and let $G$ be obtained from $H$ by gluing on vertex-disjoint triangles. For two triangl…

$K_6$ minor conjecture. 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.

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.

Tree-independence conjecture. For any two integers $k,t\in\mathbb{N}$ there exists an integer $r$ such that every graph with induced matching treewidth at most $k$ and no induced s…

Structural reformulation. Graphs in ${\cal G}_0$ induce neither $\theta$ nor $\theta^-$.

The monadic dependence conjecture. For every hereditary class $d4a2$ of structures, FO model checking is FPT on $d4a2$ if and only if $d4a2$ is monadically dependent.

A crumby coloring of a graph is a red-blue vertex coloring in which the blue subgraph has maximum degree at most $1$ and the red subgraph has minimum degree at least $1$ and contai…

Let $f$ and $g$ be polynomials. For integers $r,p\geq 0$, set … Let $G$ be a graph and let $W$ be an $R$-wall in $G$. A flat wall is a wall that is flat in the relevant surface dec…

The subcontraction conjecture. If $G$ is a facially $3$-colorable graph which does not have a subcontraction isomorphic to $K_{3,n}^+$ for some $n\geq 4$, then $G$ is $3$-flowable.

Let $t\geq 1$ be an integer. For a graph class $\mathcal{G}$, let $\operatorname{col}_\star(\mathcal{G})$ be the least integer $t$ for which there is a constant $C\geq 1$ such that…