69 problems

Let $p,q$ be positive integers with $p\geq 1$ and $q\geq 2$, and let $i\leq p$ and $j\leq q$. Let $\Psi$ be a family of graphs for which recognizing generating subgraphs isomorphic…

Feasible indexing conjecture. There exists an indexing satisfying this successor-set ordering and, whenever two consecutive nodes have equal successor-set order,

Polynomial-time computation conjecture. The following problem can be solved in polynomial time: given a graph $G \in \mathcal{G}(\widehat{C}_{6},\widehat{C}_{7})$, output $WCW(G)$.

Xu et al.'s conjecture. The maximum forcing number of $G$ can be computed in polynomial time.

Polynomial-time dimension conjecture. The dimension of a poset given its linear extension graph can be determined in polynomial time.

Gartland and Lokshtanov's conjecture. For every fixed $r$ and CMSO$_2$ formula $\psi$, $(\operatorname{tw} \leq r,\psi)$-MWIS and $\operatorname{lcol}(3)$ can be solved in polynomi…

Let $\mathscr C$ be a hereditary class of graphs. A class is dependent if it has the model-theoretic non-independence property, and first-order model checking is fixed parameter tr…

Worst-case output-size conjecture. For every $\varepsilon>0$, there exists a sourceless digraph $D$ such that, for every vertex $v$ of $D$, every quasi-kernel returned by the algor…

Small Quasi-Kernel Conjecture. The digraph $D$ contains a quasi-kernel of order at most $\frac{n}{2}$.

Let $W_{t\times t}$ be the $t$-by-$t$ hexagonal grid and let $K_{t,t}$ be the complete bipartite graph with both sides of the bipartition of size $t$. For a positive integer $t$, l…

Let $D$ be a connected plane digraph and let $k$ be an integer. The Directed Plane Strong Connectivity Augmentation problem asks whether there is a set $X\subseteq V(D)^2$ with…

Let $H$ be a simple graph. In Max Partial $H$-Coloring\, the input is a graph $G$ with a revenue function $\mathsf{rev}:V(G)\times V(H)\to\mathbb{Q}_{\geq 0}$, an…

NP-hardness conjecture. Minimum Eternal Vertex Cover is NP-hard on series-parallel graphs.

Quadratic-logarithmic lower-bound conjecture. There exist instances of the textsc{Pebble Motion Problem on Trees} for which the length of the shortest solution sequences is

The monadic dependence model-checking conjecture. For every monadically dependent class $\mathscr{C}$ there is a constant $c\in\mathbb N$ and an algorithm that, given a graph…

Hanauer et al.'s conjecture. If $\Delta\leq 5$, then

Hanauer's conjecture. If $\Delta\leq 5$, then

Let $D$ be a semicomplete digraph, and let $x,y$ be distinct vertices of $D$. A longest $(x,y)$-path is an $(x,y)$-path containing the maximum possible number of arcs. Longest path…

Let $k$ be a positive integer, and call a graph an obstruction for the class of $k$-letter graphs if it is not a $k$-letter graph while all of its proper induced subgraphs are $k$-…

Let $G$ be a bipartite graph, and let $t$ denote the number of guards in the eternal domination game. The decision problem $\textsc{Fast-Strategy}$ asks whether the guards have a s…

Let $T$ be a tournament, and let $\operatorname{\overrightarrow{\omega}}(T)$ denote the minimum, over all orderings of $V(T)$, of the clique number of the corresponding backedge gr…

Odd-bridge conjecture. If the bridge of $T$ has odd length, then no maximal non-bipartite arrangement is a maximum arrangement; equivalently,

Slow-decay conjecture. The proportion decays according to

Weak bipartition conjecture. The same limiting assertion as in the strong bipartition conjecture holds with merely $c>0$; equivalently, the asymptotic proportion is positive.

Strong bipartition conjecture. The limit exists and is a positive constant: