123 problems

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

The path-matrix conjecture. If $M$ is 2-connected, then its path matrix has exactly one positive eigenvalue.

Kriesell's conjecture. There exists a smallest integer $g(k)$ such that every $g(k)$-connected graph $G$ contains a spanning tree $T$ for which

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…

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…

West–Wu's conjecture. For every positive integer $k$, if $T$ is $3k$-edge-connected in $G$, then $G$ admits $k$ pairwise edge-disjoint $T$-connectors.

Let $Y$ be a graph, let $\overline{Y}$ be its complement, and let $\operatorname{Acyc}(\overline{Y})$ denote the acyclic orientations of $\overline{Y}$. Let…

Kawarabayashi–Ozeki conjecture. There exists a function $f(k,l)$ such that, for every $f(k,l)$-connected graph $G$ and two distinct vertices $s$ and $t$ in $G$, there are $k$ inter…

Thomassen's partition conjecture. For every $k\in\mathbb{N}$ there exists $f(k)\in\mathbb{N}$ such that if $G$ is an $f(k)$-connected graph and $M\subseteq V(G)$ consists of $k$ ve…

Baker–Rumely's lower bound conjecture. There is a universal constant $C>0$ such that, for every metrized graph $\Gamma$,

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

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…

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