45 problems

Maxmaxflow chromatic-root conjecture. There exist universal constants $C(\Lambda)<\infty$ such that every chromatic root of every loopless graph of maxmaxflow $\Lambda$ lies in

Let $G$ be a loopless graph with maxmaxflow $\Lambda$, and let $P_G(q)$ be its chromatic polynomial. Maxmaxflow chromatic positivity conjecture. For every real $q>\Lambda$, … In pa…

Let $G$ be a loopless graph with maxmaxflow $\Lambda$, and let $P_G(q)$ be its chromatic polynomial. Maxmaxflow derivative-positivity conjecture. The polynomial $P_G(q)/q$ and all…

Let $G$ be a graph and let $\Lambda(G)$ be the maximum number of edge-disjoint paths joining any pair of vertices of $G$. Sokal's conjecture. There exists a constant $C$ such that…

Let $G$ be a graph, let $\Delta(G)$ denote its maximum degree, and let $P(G,t)$ be its chromatic polynomial. Sokal's conjecture. … for every complex number $t$ satisfying … This wo…

Let $G$ be a planar bipartite graph, and let $P(G,t)$ be its chromatic polynomial. Let $\tau=(1+\sqrt{5})/2$ be the golden ratio. Salas–Sokal conjecture. … Equivalently, planar bip…

For each integer $r\geq2$, define the Beraha number … A plane triangulation is a loopless plane graph whose faces all have size three. Beraha's conjecture. For every $r\geq2$ and e…

A plane triangulation is a loopless plane graph in which every face has size three. Let $P(G,t)$ be its chromatic polynomial, let $\tau=(1+\sqrt{5})/2$ be the golden ratio, and let…

Let $G$ be a loopless planar graph, and let $P(G,t)$ be its chromatic polynomial. Thomassen's conjecture. The real chromatic roots of planar graphs are dense everywhere in … Real c…

Let $G$ be a hamiltonian loopless graph with $n$ vertices, and let $P(G,t)$ denote its chromatic polynomial. Thomassen's conjecture. … The conjecture extends the known zero-free in…

Let $G$ be a loopless 3-connected graph with $n$ vertices, and let $P(G,t)$ be its chromatic polynomial. Let $\alpha\approx 1.781$ be the chromatic root of $K_{3,4}$ in $(1,2)$. Th…

Let $L$ be the width of a triangular-lattice strip with cylindrical boundary conditions, let $B_k$ denote the Beraha numbers, and let $D(q)$ be the amplitude matrix. Cylindrical-st…

Let $L$ be the width of a triangular-lattice strip with free, cylindrical or “zig-zag” boundary conditions. Let $B_2,\ldots,B_{L+1}$ be the corresponding Beraha numbers, let…

Let $G$ be a graph of order $n$, and let $P(G,x)$ denote its chromatic polynomial. For $x<0$, the quantity $(-1)^nP(G,x)$ is positive, so its logarithm is defined. Dong–Ge–Gong–Nin…

Let $G=([[200~\ell], E)$ be a simple graph on $\ell$ vertices, and let $\mathcal{A}_G^q$ be its $q$-deformation of graphic arrangement. Write $\chi(\mathcal{A}_G^q,t)$ for its char…

For each integer $n\geq 1$, let $\mathsf{S}_n(-1)=\{P_G(-1):G\text{ is a simple graph on }n\text{ vertices}\}$. Since $|P_G(-1)|$ counts acyclic orientations of $G$, the spectrum c…

Let $G$ be a graph, let $\mathcal{A}_G^q$ be its $q$-deformed graphical arrangement, let $\chi(\mathcal{A}_G^q,t)$ denote the characteristic polynomial of this arrangement, and let…

Counting conjecture. For all sufficiently large $t$ and every $(k+t)$-fold cover $\mathcal{H}$ of $G\vee K_t$, the number of proper $\mathcal{H}$-colorings of $G\vee K_t$ is at lea…

Let $\Sigma_1$ and $\Sigma_2$ be signed complete graphs. Write $\Sigma_1\cong\Sigma_2$ when they are isomorphic, and let $\mathscr B(\Sigma,x,y)$ and $\mathsf E(\Sigma,x,y)$ denote…

For each integer $n\geqslant 0$ and each vector $\bm{a}\in\{-1,0,1\}^n$, let $\mathcal{T}_{\bm{a}}$ be the associated signed threshold graph, with bivariate chromatic polynomial…

A signed graph is a graph whose edges are assigned positive or negative signs; its bivariate chromatic polynomial is denoted by $\mathscr B(\Sigma,x,y)$, and its chromatic polynomi…

Let $G$ be a graph, let $w$ be a vertex of $G$ with $d(w)\geq 1$, and let $H$ be obtained from $G$ by deleting all but one of the edges incident to $w$. Dong's one-edge-at-a-vertex…

Let $G$ be a graph and let $w$ be a vertex of $G$. Write $G-w$ for the graph obtained by deleting $w$, and let $K_1$ be the one-vertex graph. Dong's vertex-isolation conjecture. On…

Let $G$ be a $k$-chromatic $l$-connected graph on $n$ vertices, where $k\geq 4$ and $l\geq 3$, and let $P(G,x)$ denote its chromatic polynomial. Engbers–Erey–Fox–He conjecture. For…

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…