20 problems

McCarty's conjecture. The tree-length of $G$ is small if and only if its McCarty-width is small.

Hliněný–Kwon–Obdržálek–Ordyniak conjecture. The class $\mathcal{C}$ has bounded rank-depth if and only if there exists an integer $t$ such that no graph $G\in\mathcal{C}$ contains…

Freedman–Lovász–Schrijver conjecture. Edge reflection positive graph parameters should admit a characterization analogous to the characterization of vertex-coloring-model partition…

Let $\rho$ be a graph parameter, and let $\alpha$-$\rho$ denote its independence variant, obtained by replacing the size constraint in the definition of $\rho$ with a constraint on…

Let $\mathcal{G}$ be a graph class. For graph parameters $\rho$ and $\omega$, say that $\mathcal{G}$ is $(\rho,\omega)$-bounded when bounded clique number in $\mathcal{G}$ implies…

Brimkov's conjecture. For every integer $d\geq 2$,

Let $G$ be a graph, let $\operatorname{td}(G)$ denote its treedepth, and let $\operatorname{lc}(G)$ denote its linear chromatic number. Kun–O'Brien–Pilipczuk–Sullivan's conjecture.…

Let $\mathsf{p}:\mathcal{G}_{\text{all}}\to\mathbb{N}$ be a minor-monotone graph parameter. A finite universal obstruction for $\mathsf{p}$ is a finite set of pairwise non-comparab…

Uncrossed-number separation conjecture. The uncrossed number can be arbitrarily far apart from the outerthickness. This conjecture asks whether the difference between these two gra…

Let $\mathcal{H}$ be a graph class and let $\mathcal{H}\text{-}\mathsf{p}$ be a graph parameter associated with it. The paper considers universal obstructions and obstructing sets…

Liu–Montgomery's crux conjecture. There exists some constant $c>0$ such that every graph $G$ contains a subdivision of a clique with at least

For a graph $G$, let $h(G)$ be the largest integer $kgeq 0$ such that $G$ has $k$ vertices of degree at least $k$. The universal $h$-index characterization conjecture. The characte…

Let $G$ be a graph in the class of $P_7$-free bipartite graphs. The bounded symmetric-difference conjecture. The symmetric difference is bounded in the class of $P_7$-free bipartit…

$Z(d)$ conjecture. For odd $d\geq 21$,

Let ${\cal G}$ be a non-trivial minor-closed graph class. For a positive integer $t$, let ${\cal L}_{{\cal G},t}$ be the class of graphs constructed from two disjoint paths…

Mixed partition function invariant-theoretic characterization conjecture. The multiplicative graph parameters $f$ satisfying

Mixed partition function characterization conjecture. Mixed partition functions form the entire class of graph parameters that take value $1$ on the empty graph and have finite edg…

Let $\mathcal{G}(n,p)$ be the binomial random graph, and suppose that $p$ is above the threshold of connectivity. The hyperbolicity of a graph is the graph parameter measuring the…

Shedding-diameter conjecture. With high probability,

Let a graph parameter be called testable when it is determined asymptotically by the convergence of a convergent graph sequence, as in the preceding discussion of the parameters…