17 problems

Let $d53d$ be a proper vertex-minor-closed class of graphs. For $k,p displaymath in mathbb{N}$, a graph is $k$-rank-connected if it has at least $2k$ vertices and satisfies … f…

Let $p=\omega(1/\sqrt n)$ with $p\leq 1/2$, and let $G$ be sampled from either $\mathbb{G}(n,p)$ or $\mathbb{G}(n,1-p)$. A graph is $k$-vertex-minor universal if every graph on any…

Kanté and Kwon's conjecture. A vertex-minor-closed class of graphs has bounded linear rank-width if and only if it does not contain some tree.

Kanté–Kwon conjecture. For every tree $T$, the class of $T$-vertex-minor-free graphs has bounded linear rank-width.

Vertex-minor Ramsey number conjecture for $k=5$.

Vertex-minor universality conjecture. If

A graph class is vertex-minor-closed if it contains every vertex-minor of each of its graphs. Geelen's simulation conjecture. Measurement-based quantum computation (MBQC) is effici…

Let $R_{\mathrm{vm}}(k)$ be the smallest value $n$ such that every $n$-vertex graph contains an independent set of size $k$ as a vertex-minor. Vertex-minor Ramsey conjecture.…

A graph class is proper vertex-minor-closed if it is closed under vertex-minors and is not the class of all graphs. It is linearly degree-bounded if there is a linear bound, in the…

Let $\mathcal{F}$ be a proper vertex-minor-closed class of graphs, let $G$ be an $n$-vertex graph in $\mathcal{F}$, and let $\omega$ be an upper bound on the clique number of $G$.…

Let $G$ be an $n$-vertex circle graph, and let $\operatorname{CZ}(G)$ denote its CZ-distance. Circle-graph lower-bound conjecture. There exist $n$-vertex circle graphs $G$ with … T…

The CZ-distance and CZ-complexity of a graph are the two graph-state preparation measures defined in the paper, with CZ-complexity additionally allowing arbitrarily many measuremen…

For a graph $G$, let $\tau(G)$ be its biclique number, and call a graph a vertex-minor of $G$ if it can be obtained by taking induced subgraphs and performing local complementation…

Linear 2-control conjecture. Every proper vertex-minor-closed class of graphs is linearly 2-controlled.

A graph class $\mathcal G$ is polynomially chi-bounded if there is a polynomial $f$ such that every induced subgraph $J$ of every graph in $\mathcal G$ satisfies…

For a graph $H$, let a graph class be $\chi$-bounded if the chromatic number of every graph in the class is bounded by a function of its clique number. The first author's conjectur…

Shrub-depth characterization conjecture. The class $\mathcal{C}$ is of bounded shrub-depth if, and only if, there exists an integer $t$ such that no graph $G\in\mathcal{C}$ contain…