90 problems

Almost-all-graphs unimodality conjecture. For almost all graphs $G$, the sequence $c^{\mathcal{P}}_i(G)$, $0\leq i\leq n(G)$, is unimodal.

Let $D$ be an orientation of a complete multipartite graph, and let $r$ be the number of its parts having odd size. Write $A_D(t)$ for the Eulerian polynomial of $D$, and let…

Let $G$ be a graph, and define $\nu(G)$ as the absolute value of $A_D(-1)$ for any orientation $D$ of $G$. An Eulerian graph is a graph in which every vertex has even degree. Euler…

Harary-polynomial comparability conjecture. Either $\chi_{\mathcal P}$ and $\chi_{\mathcal Q}$ are d.p.-equivalent or they are d.p.-incomparable.

Let $B_n$ be the book graph with parameter $n$, and let $D(B_n,x)$ denote its domination polynomial. The numerical data suggest the following parity-dependent statement. Real-root…

Let $H$ be a bipartite graph, and let $\widetilde{T}_H(x,y)$ denote its normalized Tutte polynomial. Assume that every vertex of $H$ has degree at least $2$. Merino–Welsh conjectur…

The preceding theorem gives a bound on rooted $K_{3,3}$ minors; denote this bound by the quantity appearing in Theorem. Tightness conjecture. The bound in Theorem is tight. This co…

Let a weakly Eulerian graph or digraph be given, and for each integer $k$ let the number of its partitions into $k$ circuits be counted. Circuit-partition unimodality conjecture. F…

Let $q_G(x)$ denote the interlace polynomial of a graph $G$. There are constants $c_1,c_2,\ldots$ with … such that, for every $k\geq 1$ and all sufficiently large $n$, there are gr…

For a connected undirected graph $G$, let $T(G;x,y)$ denote its Tutte polynomial and let $\EuScript{K}(G)$ denote its critical group. Non-determination conjecture. There exist conn…

Let $G$ be a finite claw-free graph, meaning that it has no induced subgraph isomorphic to $K_{1,3}$. Let $Z(w)$ be the hard-core lattice-gas partition function of $G$. Hamidoune–S…

Zero-divisor graph unimodality conjecture. The independence polynomial $I\bigl(\varGamma(\mathbb{Z}_n),x\bigr)$ is unimodal. The paper presents this as a conjecture following compu…

Spanning-forest Rayleigh conjecture. For any graph $G=(V,E)$, the SFGF $F_G(\mathbf{w})$ is Rayleigh.

Let $G$ be a finite simple undirected graph with vertex set $V(G)$, let $n=|V(G)|$, and let $d_k(G)$ denote the number of dominating sets of $G$ of size $k$. The polynomial … recor…

Harary almost-completeness conjecture. There is no Harary polynomial which is almost complete for $\mathbb{G}(n,1/2)$.

Bollobás–Pebody–Riordan conjecture. For the model with $p(n)=1/2$, the chromatic polynomial is almost complete.

Bollobás–Riordan completeness conjecture. The Bollobás–Riordan polynomial of the Heegaard graph of lens spaces is a complete invariant for lens spaces.

Join zero conjecture. The polynomial $g_{K_{2+r}\vee\overline{K}_{s+r}}(t)$ has a zero of order $s$ at

Complete multipartite formula conjecture. Their Speyer polynomials are

Prism and Möbius ladder conjecture. Their Speyer polynomials are

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

Let $P_k$, $P_\ell$, and $P_m$ be paths of lengths $k$, $\ell$, and $m$, respectively, and let $G$ be the graph obtained by identifying the three starting nodes and the three endin…

Let $G=(V,E)$ be a graph, and let $h^*(\mathbb{C}_G;z)$ denote the $h^*$-polynomial of its cosmological polytope. For polynomials with nonnegative coefficients, write $f\preceq g$…

Ultra log-concavity conjecture. For every graph $G$, $D(G,x)$ is ultra log-concave.

Let $G$ be an undirected graph, and let $P_G$ denote the spanning tree generating function corresponding to $G$. A polynomial is homaloidal if its polar map is birational. Chordali…