199 problems

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…

Let $G$ be a graph and let $S\betasubseteq V(G)$. The set $S$ is $2k$-edge-connected if no set of fewer than $2k$ edges separates vertices of $S$. An $S$-tree is a tree in $G$ cont…

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

Let $G^+$ and $G^-$ be two copies of a finite graph $G$ with vertex labels $[n]:=\{1,\ldots,n\}$. For $H\subseteq[n]$, form the bunkbed graph $G^\pm=(V^\pm,E^\pm)$ with…

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 $G$ be a connected $d$-regular graph, let $\tau(G)$ denote the maximum number of edge-disjoint spanning trees contained in $G$, and let $\lambda_{2}(G)$ be the second-largest e…

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

Let $G$ be an $n$-vertex 4-connected planar triangulation, meaning a planar triangulation that remains connected after the removal of fewer than four vertices. A Hamiltonian cycle…

Frank's conjecture. A graph $G$ has a $k$-connected orientation if and only if, after deleting any set of $j<k$ vertices, it remains $(2k-2j)$-edge-connected.

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

Halin's conjecture. There is a constant $c_k$ such that every minimally $k$-connected graph $G$ has at least $c_k|V(G)|$ vertices of degree $k$.

Let $G$ be a 4-connected toroidal graph, meaning a $4$-connected graph embedded on the torus. The Grünbaum–Nash-Williams conjecture. $G$ is hamiltonian. The conjecture extends the…

Gupta–Kumar connectivity conjecture. The graph

Let $k$ be a positive integer. A tournament is a directed graph in which exactly one of $xy$ and $yx$ is an edge for every pair of distinct vertices $x,y$. A tournament is $k$-link…

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

Brouwer's conjecture. The vertex-connectivity of $G$ equals its degree:

Let $d\geq 1$, let $G$ be a $d$-vertex-connected graph, and let $r$ be a vertex of $G$. A family of spanning trees $T_1,\ldots,T_d$ is said to provide independent paths from $r$ if…

Let $G$ be a $k$-vertex-connected graph, and let $r$ be any root of $G$. A collection of spanning trees $T_1,\dots,T_k$ is independent with root $r$ if, for every vertex…

Fujita–Kawarabayashi conjecture. There is a least non-negative integer $f_k(m)$ such that every $k$-connected graph $G$ with

Connectivity threshold conjecture. For the $G^{(k)}(n,r)$ filtered graph,

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…

Let $n$, $\delta_1$, and $\delta_2$ be positive integers, and let $c>0$ be a constant. Sharpness conjecture. There exists a constant $c>0$ such that, for every triple satisfying ……

Piecewise extremal edge-bound conjecture. If $G$ has no $(k+1)$-connected subgraph, then

Zero-one law for k-connectivity. There should exist a zero-one law for $k$-connectivity analogous to the zero-one law for the minimum node degree being at least $k$.