134 problems

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

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…

Let $d\ge 1$. For a finite graph $\mathbf{G}$, let its diameter be the maximum distance between two vertices, let its connectivity be the minimum number of vertices whose removal d…

For a fixed integer $q\ge 3$, let $n_0(q)$ be an integer threshold. Let $G$ be a 2-connected graph of order $n\ge n_0(q)$, and write $\delta(G)$ for its minimum degree. Liu and Nin…

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…

A digraph $D$ is $k$-strong if it has at least $k+1$ vertices and remains strongly connected after the deletion of any set of at most $k-1$ vertices. An orientation of a digraph is…

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…

Bang-Jensen–DeVos–Mütze conjecture. Every $(2k-1)$-strong semicomplete digraph on at least $2k+1$ vertices contains a spanning $k$-strong tournament.

Jackson–Thomassen conjecture. Every $2k$-strong digraph has a spanning $k$-strong oriented subdigraph.

Let $k \ge 3$ and $n \ge 2k$ be integers, and let $G$ be a matchable $k$-connected graph with $n$ vertices. Zaks's conjecture. Every such graph satisfies … moreover, infinitely man…

Yokoi's conjecture. There exists a constant $d$ satisfying the preceding condition: for every $2$-connected graph $G$ of odd order with minimum degree at least $d$, one has…

3-connected minimum-degree conjecture. If

Let $G$ be a $5$-connected non-planar graph with at least seven vertices. Kawarabayashi–Maharry conjecture. The graph $G$ contains both a $K_{3,4}$ minor and a $K_6^-$ minor. The s…

Connectivity conjecture for tilted Bruhat posets. The poset defined in the source by $\ell_{\mathbf{a}}(w)$ is connected, and $\lesssim_{\mathbf{a}}$ is connected when restricted t…

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

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

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…

A graph is well-balanced oriented when it has an orientation in which, for every pair of vertices, the maximum number of edge-disjoint directed paths from the first vertex to the s…