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

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.

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…

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…