12 problems

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)$.

Independence-polynomial conjecture. Then $G$ is a well-covered tree. This concerns whether a well-covered tree is characterized, among connected graphs, by its independence polynom…

Independence-polynomial characterization conjecture. If $T$ is a well-covered tree and $I(T;x)=I(G;x)$, then $G$ is well-covered.

The 2-quasi-regularizability characterization. $G$ is $2$-quasi-regularizable if and only if

Levit–Tankus conjecture. The graph $G$ is $\mathbf{W_2}$ if and only if, for every vertex $v$ in $G$ and every maximal independent set $S$ in $G-N[v]$, the largest independent set…

$\mathbf{W_2}$ characterization conjecture. For every graph $G$, the following assertions are equivalent:

Let $G$ be a connected graph, let $T$ be a well-covered tree, and let $I(G,x)$ denote the independence polynomial of $G$. Levit–Mandrescu conjecture. If … then $G$ is a well-covere…

Relating-edge recognition conjecture. The following problem is polynomially solvable: given a graph $G \in \mathcal{G}(\widehat{C}_{6})$ and an edge $xy \in E(G)$, determine whethe…

Prism necessity conjecture. If $G \Box K_2$ is well-covered, then $G$ has no isolatable vertex.

Let $G$ be a $1$-well-covered graph, let $\alpha(G)$ be its independence number, let $n=|V(G)|$, and write $I(G;x)=\sum_k s_kx^k$ for its independence polynomial. Roller-Coaster Con…

Let $\alpha\geq2$ and $n\geq4$ be integers satisfying … For a graph $G$, let $\alpha(G)$ denote its independence number, let $|V(G)|$ denote its order, and write…

Zaare-Nahandi's conjecture. $G$ is semi-perfect.