146 problems

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…

Let $G$ be a very well-covered graph of order $n$, meaning that every maximal independent set has size $n/2$, and let … be its independence polynomial. Levit–Mandrescu's conjecture…

An orientable ribbon graph is a graph embedded in an orientable surface, and its partial-dual polynomial records the genera of all partial duals, with coefficients counting partial…

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

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…

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

Collins' conjecture. The sequence of coefficients of $CPA(T)$ is unimodal, and its peak $p_A(T)$ occurs at the same place as $p_D(T)$.

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

The flow polynomial and the golden identity are considered for cubic graphs; the golden identity is the flow-polynomial analogue of the corresponding identity for the chromatic pol…

Let $G$ be a graph, and let $D(G,x)$ denote its domination polynomial. An integer root is an integer number $r$ such that $D(G,r)=0$. Integer-root conjecture. Every integer root of…

A genus polynomial is the polynomial whose coefficients record the genus distribution of a graph. Stahl's conjecture. Every genus polynomial is real-rooted. This conjecture was dis…

Loebl's conjectures. The q-dichromate is equivalent to the U-polynomial, and the q-dichromate distinguishes non-isomorphic chordal graphs. Equivalently, in the latter assertion, eq…

Conjectured formulas.

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…

Complex zero-free-domain conjecture. There exists a complex domain $D_r$ containing the real interval $(2r,\infty)$ such that

Generalized connected-sum monotonicity conjecture. If $|1+v_e|\leq 1$ for every edge $e$, then $|C_G(\lambda,\{v_e\})|$ is a decreasing function of $\lambda$ on…

Let ${\cal B}$ be the limiting zero set for a strip of width $L$, let $\#E$ be its number of endpoints, let $\#C$ be its number of connected components, and let $\#Q$ be its number…

The width-two strip conjecture. The family $2_{\rm P}\times n_{\rm F}$ possesses this property for every finite length $n$. The observation at $w=-1/2$ supports the conjecture, but…

Sokal's conjecture. Every loopless graph has the multivariate Brown–Colbourn property. This strengthens the univariate Brown–Colbourn conjecture by requiring simultaneous zero-free…

Sokal's conjecture. The absolute-value signs can be put outside the sum:

For a cyclic or Möbius square-lattice strip of width $L_y\geq 2$, let $q_{cf}$ denote the real-axis threshold associated with the limiting locus of the flow-polynomial zeros. The a…

Let $G$ be a series-parallel graph, and let $P_G(q)$ be its chromatic polynomial. Write $p$ for the relevant graph parameter in the proposed $p/\log p$ bound, and distinguish maxim…

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…