123 problems

Exact-value conjecture. Under these conditions,

Let $G$ be a cyclically 4-connected cubic graph, and let $F(G,t)$ denote its flow polynomial. Let $\tau=(1+\sqrt{5})/2$. Finiteness conjecture. For every $\epsilon>0$, only finitel…

Let $G$ be a 3-connected graph with $n$ vertices and $m$ edges, and let $F(G,t)$ denote its flow polynomial. Let $\phi\approx1.749$ be the flow root of $K_5$ in $(1,2)$. 3-connecte…

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…

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…

Maxmaxflow conjecture. There exist universal constants $C(k)<\infty$ such that every chromatic root $z$ of any graph $G$ with $\Lambda(G)=k$ lies in the disc

Connectivity-shell hypothesis. When the unfolding process is fully developed, the infinitesimal neighborhood of $S_0$ is densely connected to it, and connectivity decreases through…

Let $D$ be a strongly connected digraph with $n\geq 3$ vertices and $m$ arcs. An acyclic separator is a separator whose induced subdigraph is acyclic. Extremal arc-count conjecture…

Combinatorial-zeolite conjecture. Every 6-connected 3-dimensional combinatorial zeolite is globally rigid in $\mathbb{R}^3$.

Six-connectivity conjecture. Every 6-connected $K_4$-covered graph is rigid in $\mathbb{R}^3$.

Hasunuma's conjecture. If

Cheeger-constant Nordhaus-Gaddum conjecture. If $G\neq S_n$, then

Let $G$ be a $k$-connected graph on $n$ vertices with minimum degree $\delta(G)\ge k+2$. A matching is $k$-removable when deleting its edges leaves a $k$-connected graph. The maxim…

For $k\ge 1$, a vertex set $S$ in a $k$-connected graph $G$ is $k$-removable when $G-S$ remains $k$-connected; a matching is $k$-removable when its edge deletion leaves a $k$-conne…

For $k\ge 1$, let $T$ be a tree of order $m$, and let $G$ be a $k$-connected or $k$-edge-connected graph with minimum degree $\delta(G)\ge k+m-1$. A subtree $T'$ is isomorphic to…

For $k\ge 1$ and any tree $T$ of order $m$, let $G$ be a $k$-connected graph with minimum degree $\delta(G)\ge \left\lfloor 3k/2\right\rfloor+m-1$. A subtree $T'$ is isomorphic to…

Planar Circular Flow Conjecture. Every $4k$-edge-connected planar graph admits a circular $(2+\frac{1}{k})$-flow.

Ryjáček et al.'s conjecture. Every $4$-connected line graph with minimum degree at least $5$ is Hamiltonian.

Ryjáček et al.'s conjecture. Every $4$-connected ${K_{1,4},K_{1,4}+e}$-free graph with minimum degree at least $6$ is Hamiltonian.

Let $s\geq 3$ and let $\mathcal{D}_{s,n}$ be the $(1:b)$ Maker–Breaker game on the edges of $K_n$ in which Maker wins precisely when her spanning subgraph has diameter at most $s$.…

Let $k\in\mathbb{N}$, let $G$ be a connected graph with $tw(G)\leq k$, and let $xy\in E(G^c)$. A $k$-ghost-edge is a nonedge $xy$ such that every tree decomposition…

Godsil's conjecture. If $G$ is a connected graph which is a colour class in an association scheme, then

Let $G$ be a graph, and let $\mathcal{F}(G,k)$ denote its reconfiguration graph whose vertices are nowhere-zero $k$-flows, with adjacency given by changing flow values only on a cy…

Let $d$ be a positive integer, and let $G$ be a graph on $n$ vertices. Write ${\mathcal{S}}_d(G)$ and ${\mathcal{H}}_d(G)$ for the completability and hyperconnectivity matroids in…