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

Let $G$ be a graph, and let $k\geq 2$ be an integer. A collection of $k$ spanning trees of $G$ is called a collection of completely independent spanning trees if, for every pair of…

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.

Let $G$ be a 6-connected simple graph. A graph is 1-apex if deleting one vertex makes it planar, and $K_6$ denotes the complete graph on six vertices. Jørgensen's conjecture. Every…

Robertson's conjecture. The Petersen graph is the only non-bipartite pentagraph that is $3$-connected and internally $4$-connected.

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

Let $G$ be a $k$-connected graph. A longest path is a path of maximum length in $G$. Hippchen's conjecture. Every pair of longest paths in $G$ intersect in at least $k$ vertices. T…

Let $G$ be a graph, let $\alpha(G)$ be its independence number, and let $c(G)$ be the number of cut-vertices of $G$. Graffiti's cut-vertex conjecture. … The paper verifies this ine…

Kelmans–Seymour conjecture. Every 5-connected nonplanar graph contains $TK_5$.

Let $\mathcal{G}$ be a bridge-addable class of labeled graphs with $n$ vertices, meaning that whenever $G\in\mathcal{G}$ and an edge has endpoints in two distinct connected compone…

Let $G$ be an $r$-connected graph with $r\ge 2$. A longest cycle is a cycle in $G$ of maximum length. Smith's conjecture. Every pair of longest cycles in $G$ intersects in at least…

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…

Lovász–Yemini conjecture. There exists an integer $c_d$, possibly $c_d=d(d+1)$, such that every $c_d$-connected graph is $d$-rigid.

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

A digraph is semicomplete if it has no pair of non-adjacent vertices. A tournament is an orientation of a complete graph, hence a semicomplete digraph with no directed 2-cycles. A…

Let $G$ be a $2$-connected graph with minimum degree at least $3$, and let a longest cycle mean a cycle of maximum length in $G$. Harvey's conjecture. Every longest cycle of $G$ ha…

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.

Let $W$ be a connected graphon and $K\in\mathbb{N}$. For each $n\in\mathbb{N}$, consider the $W$-edge-incremental process $\mathfrak{X}_n=(G_n^t)_{t=0}^{\binom{n}{2}}$ of order $n$…

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

Borradaile et al.'s conjecture. A strong orientation of $G$ is decreasingly minimal among strong orientations if and only if there is no small improvement preserving strong connect…

Bollobás–Gyárfás conjecture. If $n>4(k-1)$, then every 2-coloring of $K_n$ contains a monochromatic $k$-connected subgraph of order at least

Connectivity conjecture. Setting $K_{\mathrm{avg},n}$ to any finite number larger than or equal to two should be sufficient to ensure that $\mathbb{H}(n; \pmb{\mu}, \pmb{K}_n)$ is…

A graph is 5-connected if deleting fewer than five vertices leaves it connected, and it is nonplanar if it cannot be drawn in the plane without crossings. A $K_5$-subdivision is a…

Li's conjecture. For an integer $\ell$ with $2\leq \ell\leq n-2$, deciding whether