39 problems

Let $F$ be a forest, and let $I_F(t)$ denote its independence polynomial, whose coefficients count independent sets of each cardinality. Alavi–Malde–Schwenk–Erdős conjecture. For e…

Kalai–Meshulam conjecture. Every ternary graph satisfies

Let $G$ be a well-covered graph, meaning that all maximal independent sets of $G$ have the same cardinality, and let $I_G(t)$ denote its independence polynomial. Brown–Dilcher–Nowa…

Let $q$ be a positive integer, let $\pi$ be a permutation of $\{\lceil q/2\rceil,\lceil q/2\rceil+1,\ldots,q\}$, and let $i_k(G)$ denote the number of independent sets of cardinali…

Hamidoune's conjecture. The independence polynomial $I(G;x)$ of any claw-free graph has only real roots. This is presented as a conjecture from 1990; the supplied text gives no res…

Let $G$ be a graph, let $s_k$ be the number of stable sets of cardinality $k$ in $G$, let $\alpha(G)$ be its stability number, and define its independence polynomial by … A polynom…

Roller-coaster conjecture. The numbers

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.

Let $G$ be a connected $\mathbf W_2$ graph, where $n(G)$ is its number of vertices and $\alpha(G)$ is its independence number. A graph is 2-quasi-regularizable when it satisfies th…

Let $G$ be a graph and let $q$ be a positive integer. Write $\mathcal{I}^{(q)}(G)$ for the set of $q$-tuples $(I_1,\dots,I_q)$ of pairwise disjoint independent sets of $G$. For tup…

Levit–Mandrescu conjecture. Every value in the allowable range given by this bound is attained by some connected graph.

The well-covered-spider log-concavity claim. $I(G;x)$ is log-concave, meaning

The independence-polynomial unimodality conjecture. $I(G;x)$ is unimodal: there exists an index $0\leq k\leq\alpha(G)$ such that

Let $G$ be a regular graph, let $P_G(\lambda)$ denote its independence polynomial, and let $|V(G)|$ be its number of vertices. For a fixed degree and girth, let the corresponding M…

Let $\Delta$ be a maximum-degree bound, and let $\mathcal{U}_{\Delta,2}$ be the maximal connected zero-free region containing $0$ for graphs of maximum degree at most $\Delta$. Per…

Let $\mathcal{U}_{\Delta,2}\subseteq\mathbb{C}$ be the maximal open zero-free set for graphs of maximum degree at most $\Delta$, and let…

Let $\mathcal{H}$ be a hypergraph of maximum degree at most $\Delta$, and let $Z(\mathcal{H};\bm{\lambda})$ denote its independence polynomial with complex vertex activities. Defin…

Galvin–McKinley–Perkins–Sarantis–Tetali conjecture. For each $k\geq 2$, there exists a constant $C_k>0$ such that, if $G$ is a $k$-uniform linear hypergraph of maximum degree…

Let $F$ be a forest, and let $I(F;x)=\sum_{k=0}^{\alpha(F)}i_kx^k$ be its independence polynomial, where $\alpha(F)$ is the independence number and $i_k$ counts the independent set…

Let $\Delta_0$ be the threshold parameter in Theorem, concerning the accumulation of chromatic zeros of leaf joined trees relative to the degree bound $\Delta$. The degree-three th…

Beaton–Brown–Cameron conjecture. If $3\not\vert n$, then a graph $G$ is independence equivalent to $C_n$ if and only if

Let $T_1$ and $T_2$ be trees of order $n$. Write $T_1\triangleleft T_2$ when the independence polynomial order satisfies the strict relation, and $T_2\trianglelefteq T_1$ for the c…

For a positive integer $n$, let $C_n$ be the cycle graph on $n$ vertices, let $D_n$ be the graph obtained from $C_n$ by adding a loop structure as defined in the paper, and let…

Let $G$ be a tree, and let $i(G,x)$ denote its independence polynomial. A polynomial is stable here when all of its roots lie in the left half-plane. Tree stability conjecture. The…