9 problems

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

For a graph $G$, let $\operatorname{tw}(G)$ denote its treewidth. A graph is even-hole-free if it has no induced cycle of even length at least four, and the diamond is the graph on…

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…

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…