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 $G=(V,E)$ be a simple graph, let … be its total domination polynomial, where $n$ is the order of $G$ and $d_t(G,i)$ counts the total dominating sets of cardinality $i$. A root…

Let $G$ be a non-orientable ribbon graph. Its partial-dual Euler-genus polynomial is the generating function … where $G^A$ is the partial dual of $G$ with respect to…

Let $\operatorname{GP}(n,k)$ be the generalized Petersen graph, and let $\operatorname{I}(\operatorname{GP}(n,k),x)$ denote its independence polynomial. For all integers…

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

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

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…

Zhang and Zhang's conjecture. The polynomial

A ribbon graph is orientable if its associated ribbon surface is orientable, and its partial duality polynomial is the generating function that enumerates its partial duals by Eule…

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…

Clique-root conjecture. If $G$ is $K_{l+3}$-free, then $G$ has only clique roots.

Let $G$ be a primitive graph with first Betti number $h_1(G)$, and let $\dim(c_2(G))$ denote the dimension of a minimal model of its $c_2$-invariant. Universal dimension-bound conj…

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…

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

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