134 problems

A graph $G=(V,E)$ is $k$-connected if it remains connected after the deletion of any set of at most $k-1$ vertices. An orientation of $G$ is $k$-strong if its corresponding digraph…

Mader's conjecture. For any tree $\T$ of order $\m$, every $\k$-connected graph $\G$ with minimum degree

Tomescu's ℓ-connected generalization.

Pokrovskiy's conjecture. For every $k\in\mathbb{N}$, there exists an integer $h(k)$ such that every $2k$-connected tournament with $\delta^0(D)\geq h(k)$ is $k$-linked.

Linear-connectivity partition conjecture. There exists a constant $c>0$ such that the vertices of every strongly $c\cdot ktl$-connected digraph $D$ with $\delta(D)\geq n-l$ can be…

Let $G=(V,E)$ be a graph and let $k$ be a positive integer. A $k$-vertex-connected orientation is an orientation of $G$ that is $k$-vertex-connected. Frank's conjecture. $G$ has a…

Jørgensen's conjecture. If $G$ is 6-connected and does not have a $K_6$ minor, then $G$ is apex.

Let $G$ be a $3$-connected graph. A set $W\subset V(G)$ is contractible if $G(W)$ is connected and $G-W$ is $2$-connected; a contractible set with $k$ vertices is called a $k$-cont…

Luo–Tian–Wu's conjecture. Every $\k$-connected bipartite graph $\G$ with

For a natural number $k$, a graph is $2k$-edge-connected if every edge cut has size at least $2k$, and an orientation is $k$-arc-connected if every ordered pair of vertices is join…

Let $G$) be a 3-connected non-Hamiltonian graph. Let $K_{3,4}$ be the complete bipartite graph, let $\mathfrak{Q}^+$ be obtained from the cube by adding a new vertex adjacent to th…

Cyclic edge-connectivity conjecture. Every $(k,g)$-cage is cyclically $(k-2)g$-edge-connected.

A graph is 3-connected if deleting fewer than three vertices leaves it connected. A chord of a cycle is an edge joining two nonconsecutive vertices of the cycle. Thomassen's chord…

Bounded nonrepetitive connection conjecture. There exists a constant $t$ such that every $2$-connected graph $G$ satisfies

Let $G$ be a graph and let $v$ be any specified vertex of $G$. A collection of spanning trees of $G$ is independent spanning trees rooted at $v$ if, for every vertex $u$, the paths…

A pseudo $2$-factor isomorphic graph is a graph admitting a $2$-factor such that the parity of the number of cycles is the same for all its $2$-factors. A graph is cubic if every v…

Lovász–Woodall conjecture. If $k$ is even or $G-S$ is connected, then $G$ contains a cycle containing every edge in $S$.

Let $Y$ be a connected bipartite graph on $n\ge 5$ vertices with no non-trivial cut edge and $Y\not=C_n$. The graph $\mathsf{FS}(K_{2,n-2},Y)$ is the friends-and-strangers graph as…

Let $Y$ be a graph on $n\ge 2k\ge 4$ vertices. A $k$-bridge is a set of $k$ edges whose deletion disconnects the graph, and it is non-trivial when neither resulting component is an…

Let $G$ be an $n$-vertex $k$-chromatic $\ell$-connected graph, and let $i_t(G)$ denote the number of independent sets of size $t$ in $G$. Fixed-size independent-set conjecture. If…

Let $G$ be an $n$-vertex $k$-chromatic $\ell$-connected graph, and let $i_t(G)$ denote the number of independent sets of size $t$ in $G$. Fixed-size independent-set conjecture. If…

Polynomial-time k-colouring conjecture. There is a polynomial-time algorithm that, given $G$, finds a $k$-colouring of $G$, or determines that none exists.

The conjecture. The maximum order of a $k$-connected subgraph using at most two colours in every $6$-colouring of $K_n$ satisfies

Let $G$ be a graph, with chromatic number $\chi$, clique number $\omega$, maximum degree $\Delta$, order $n$, and let $\overline{\kappa}=\kappa(\overline{G})$ denote the connectivi…

Let $k$ be the base field, let ${\operatorname{{\mathcal S}{\mathcal H}}}_{S^1}(k)$ be the homotopy category of $S^1$-spectra, and let $\Sigma^\infty_{{\mathbb P}^1}$ and…