13 problems

Let $G$ be a $2$-bicritical graph with two odd cycles. The polynomial-time computability claim. The sets core $\core G$ and corona $\corona G$ can be computed in polynomial time. T…

For any integer $t$ and any odd integer $k$, let $\mathcal{G}_{t,k}$ be the class of graphs that are $P_t$-free and whose induced odd cycles all have length $k$. Polynomial-time 3-…

Let $f_1,f_2\colon\mathbb{N}\to\mathbb{N}$ be functions such that, for every non-planar graph $H$ with $t=|V(H)|$, every $H$-minor-free graph admits a clique-sum decomposition into…

Let a topology be a fixed graph structure, and consider instances of the Stacker Crane Problem (SCP) whose underlying graphs have that topology. Paths and cycles are topologically…

An induced packing of cycles is a collection of cycles such that no edge joins distinct cycles. A graph class has no induced packing of $k$ cycles if no graph in the class contains…

Polynomial-time precoloring-extension conjecture. For every positive integer $\ell$, there is a polynomial-time algorithm that, given a planar near-Eulerian-triangulation $G$ with…

Bounded-independent-set conjecture. For every fixed integer $k$, the Hamiltonian-cycle problem is polynomial-time solvable for the class of split digraphs $D=(V_1,V_2;A)$ in which…

Conjecture on fixed-vertex extensions. For every fixed integer $k$, there exists a polynomial-time algorithm for deciding whether such a digraph has a Hamiltonian cycle.

Polynomial-time branchwidth conjecture. Branchwidth can be computed in polynomial time on $H$-minor-free graphs.

Recognition conjecture for trees. There is a polynomial-time algorithm that decides whether

Polynomial-time solvability conjecture. The problem of deciding whether

Let the three graph classes be the $(P_5, \overline{2P_2+P_1})$-free graphs, the $(P_5, K_{2,3})$-free graphs, and the $(P_5, \overline{K_3+O_2})$-free graphs. Here, $P_5$ is the p…

A quasi Cartesian product is a graph with the local product-like structure described above. Reconstruction conjecture. Quasi Cartesian products can be reconstructed in essentially…