89 problems

Let $G$ be a planar graph with $n$ vertices, let $P(G,k)$ denote its coloring polynomial, and let $k$ be a real number with $k\geq 4$. Birkhoff–Lewis conjecture. For every such gra…

Let $G$ be a connected graph on $n$ vertices with chromatic number $\chi(G)=k\geq 4$, and let $P(G,x)$ denote its chromatic polynomial, the number of proper $x$-colorings. Let…

Let $\Delta\geq 3$ be an integer. Consider graphs all of whose vertices have degree at most $\Delta$, except possibly one vertex, and let $Z(G;q)$ denote the chromatic polynomial o…

Let $G$ be a graph, and let $P_G(q)$ denote its chromatic polynomial, whose roots are called chromatic roots. The Beraha numbers are the numbers … A planar triangulation is a plana…

Let $G$ be a finite graph and let $\chi_G(x)$ be its chromatic polynomial. Read's conjecture. The absolute values of the coefficients of $\chi_G(x)$ are unimodal. This conjecture w…

Let $G$ be an $n$-vertex graph, and let $P(G,x)$ denote its chromatic polynomial. The mean color number $\mu(G)$ is the average number of colors used in all $n$-colorings of $G$. B…

Let $G$ be a graph of maximum degree $\Delta$, with $\Delta \ge 4$, and let $K_{\Delta,\Delta}$ denote the complete bipartite graph with $\Delta$ vertices in each part. A chromatic…

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 $\mathcal{G}$ be a class of finite graphs and let $\mathcal{V}$ be a subset of the complex plane. For a graph $G$ with edge weights $\{v_e\}$, let … For $G=(V,E)$ and distinct…

Farrell's conjecture. Every chromatic zero $q$ satisfies

Unit-disk conjecture. For these strips, there are no chromatic zeros satisfying

Global-circuit conjecture. Global circuits are a necessary condition for lattice strips to have chromatic zeros and, in the limit $L_x\to\infty$, a locus ${\cal B}$ with support fo…

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

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

Extremal generalized-theta conjecture. For every $k$, the $k$-ary generalized theta graph whose chromatic root $z$ maximizes $|z-1|$ is $\Theta^{(2,k)}$, the graph with all path le…

Let $B_m(b)$ denote the toroidal chain of complete graphs with parameter $b$, and let $\lambda_{B_m(b),3,j}$ denote the corresponding eigenvalues indexed by $j$. Consider the four…

Let $G$ be a regular lattice graph with no global circuits, let $n=v(G)$ tend to infinity, and let ${\cal B}$ denote the resulting set of points in the complex $q$-plane. Conjectur…

Let $G$ be a regular lattice graph with no global circuits, and let $q_0$ be a chromatic zero of $G$. Conjecture (1a). One has $Re(q_0)\geq 0$, and the only chromatic zero with…

Let $G$ be a graph family with limiting ground-state degeneracy per vertex … and define its reduced function by $W_r(\{G\},q)=q^{-1}W(\{G\},q)$. Let $\Lambda$ be a regular lattice…

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…