22 problems

Let $n_1\geq\cdots\geq n_k\geq 2$ and $m_1\geq\cdots\geq m_k\geq 2$. Let $T_1=T(n_1,\ldots,n_k)$ and $T_2=T(m_1,\ldots,m_k)$ be starlike trees of order $n$ and maximum degree $k$.…

Let $\mathcal{T}_n$ be the set of all trees with $n$ vertices, ordered by $\succeq$. The length of a chain is the number of elements in a sequence $T_1\succ T_2\succ\cdots$ under t…

Symmetry characterization. $I(G\circ H;x)$ is symmetric for every graph $G$ if and only if $H=K_r-e$ for some $r\geq 2$.

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 $T$ be a tree, let $\alpha(T)$ denote its independence number, and let $(a_i)_{i=0}^{\alpha(T)}$ be its independent set sequence. Log-concavity is broken at $k$ when…

Alavi–Malde–Schwenk–Erdős conjecture. The independence polynomial of every tree is unimodal.

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

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…

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…

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…

Let $\mathrm{M}$ be a matroid on a finite set $E$, write $r+1$ for its rank, and call a subset of $E$ independent if no element belongs to the closure of the other elements. Let…

A tree is a connected acyclic graph, and a forest is an acyclic graph. For a graph $G$, its independence sequence $(i_0(G),i_1(G),\ldots,i_{\alpha(G)}(G))$ records the numbers of i…

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…

Let $K_{t,n}$ be the complete bipartite graph with parts of sizes $t$ and $n$, and let $K_{t,n}\circ K_1$ denote its corona with $K_1$. Write $I(G;x)$ for the independence polynomi…

Let $\succeq$ be the order on graphs defined by comparing their independence polynomials, and let $\mathcal{T}_n$ be the set of trees with $n$ vertices. Total-order conjecture. For…

Let $V_n^{(m)}$ be the vertebrated graph, and let $I(V_n^{(m)};x)$ denote its independence polynomial. Zhu's conjecture. For $n,m$ with $n,m$ nonnegative integers, the…