14 problems

Robertson's conjecture. The Petersen graph is the only non-bipartite pentagraph that is $3$-connected and internally $4$-connected.

Induced-minor characterization conjecture. For every integer $t$ there exist integers $c,d$ such that every graph $G$ either contains $K_{t,t}$ or $\boxplus_t$ as an induced minor…

Let $t$ be a positive integer. For a graph $G$, write $\operatorname{tree-\alpha}(G)$ for its tree-independence number, and let $K_{t,t}$ denote the complete bipartite graph with…

Polynomial-separator or bounded-hole conjecture. There exists a polynomial $p$ and an integer $k$ such that if $G$ has no clique cutset and does not contain $K_{2,3}$ as an induced…

Let $G$ be an $n$-vertex graph with $e$ edges, and let a $C_{2k+1}$-edge mean an edge contained in a cycle of length $2k+1$. Assume that $e>n^2/4$, $k\geq 3$, and $n>n_k$, where…

Abrishami–Czyżewska–Kluk–Pilipczuk–Pilipczuk–Rzążewski's conjecture. Every graph class with balanced separators consisting of few neighborhoods admits tree-decompositions whose bag…

Smaller-partition conjecture. Since the analyzed graphs are small, partitioning their adjacency matrices into smaller sub-matrices should be more favorable.

Let $G$ be a finite simple graph. A graph is triangle-free if it contains no triangle, and has diameter $2$ if every two vertices are at distance at most $2$. Sparse triangle-free…

Let $\mathcal{G}$ be an arbitrary $(\operatorname{tw},\operatorname{had})$-bounded graph class, meaning that there is a function $f$ with…

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…

Let $G$ be an asymptotically extremal graph for the Ramsey–Turán density $\varrho_p(q)$, where the $p$-independence number is the largest size of a vertex set inducing a $K_p$-free…

Let $G$ be a graph, let $k$ and $Delta$ be positive integers, and let $W_{k \times k}$ denote the $(k \times k)$-wall. A subdivision of a graph is obtained by replacing its edges b…

Let $t\geq1$ and let $G$ be a graph with a maximum number of edges among graphs that do not contain cycles of $t$ consecutive even lengths. A block is a maximal connected subgraph…