35 problems

Dependence conjecture. First-order model checking is fixed-parameter tractable on every hereditary dependent class of graphs.

Let finite graphs be ordered by the minor relation. Wagner's conjecture. Every minor-closed class of finite graphs is determined by a finite set of excluded minors. Robertson and S…

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…

Abrishami et al.'s conjecture. The existence of weighted balanced separators contained in a bounded number of balls of bounded radius implies the existence of a tree-decomposition…

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…

Decomposition conjecture. Motivated by Simon's decomposition theorem of dependent types into a stable part and a distal (order-like) part, every dependent hereditary class of graph…

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 $f_1,f_2\colon\mathbb{N}\to\mathbb{N}$ be functions such that, for every non-planar graph $H$ with $t=|V(H)|$, every $H$-minor-free graph admits a clique-sum decomposition into…

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…

A graph class has bounded merge-width if, for every fixed radius $r\in\mathbb N$, its radius-$r$ merge-width is bounded by a constant. The paper identifies bounded twin-width and s…

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…

Aboulker's basic-obstruction conjecture. Basic obstructions are the only obstructions to bounded treewidth in graphs of bounded maximum degree; equivalently, after excluding the ba…

Aboulker's bounded-degree conjecture. Every class of (theta, triangle)-free graphs with bounded maximum degree has bounded treewidth, and every class of even-hole-free graphs with…

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.

Let $\mathcal{C}_t^*$ be the class of graphs with no induced $C_4$, diamond, theta, prism, even wheel, or $K_t$. Here $C_4$ is a cycle on four vertices, and the other names denote…

Plummer–Zha's closeness-to-bipartite conjecture. Every counterexample to Robertson's conjecture is close to bipartite.