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

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.

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 $\vec{H}$ be a strongly connected tournament with $k:=v(H)\geqslant 4$, and let $p\gg n^{-2/(k+1)}$. Tournament orientation-counting conjecture. Then, with high probability, ……

Let $G$ be a graph and let $F:V(G)\to 2^{\mathbb{N}}$ assign a set of forbidden outdegrees to each vertex. An orientation $O$ of $G$ is $F$-avoiding if $d^+_O(v)\notin F(v)$ for ev…

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…

Cycle-free orientation counting conjecture. With high probability as $n\rightarrow\infty$,

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…

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

For each $d\geq3$, let $p^*(d)$ be the minimum value of $p\in\{1,2,\ldots,\lfloor d/2\rfloor\}$ such that a.a.s. the random graph $\mathcal{G}_{n,d}$ has a $p$-orientation. Define…

Let $\mathcal{G}_{n,d}$ be the uniform model of random $d$-regular graphs on the vertex set $[n]=\{1,2,\ldots,n\}$. A $p$-orientation is an orientation of a $d$-regular graph in wh…

Let $G$ be a graph, and let ${\rm gp}_{\rightarrow}(G)$ denote the minimum general position number over all orientations of $G$. The lower-number-two hardness conjecture. It is NP-…

Let $G$ be a graph, and let ${\rm gp}_{\rightarrow}(G)$ be the minimum general position number over all orientations of $G$. The lower-number hardness conjecture. Determining the l…

Let $G$ be a graph, and let … be its general position spectrum. The interval-spectrum conjecture. The set $S_{{\rm gp}}(G)$ is an interval of integers. The spectrum is an interval…

Let $G$ be a connected graph of order $n\geq 3$. Define ${\rm gp}^{\rightarrow}(G)$ as the maximum general position number over all orientations of $G$, and…

Let $G$ be a graph, and let … be its general position spectrum. The nonconstant-spectrum conjecture. Every graph has two orientations with different general position numbers; equiv…

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…

Power-objective divergence conjecture. For every integer exponent $c\geq 2$, the problems with objective functions $\varphi(z)=z^c$ admit distinct sets of optimal acyclic orientati…

Conjecture on $m(n,d)$.

Koh–Tay conjecture. The graph $G$ has an orientation of diameter two. This conjecture was proved by Cochran, Czabarka, Dankelmann and Székely in 2021, so it is no longer open.

Let $H$ be a graph and let $\vec{H}$ be a directed graph with underlying graph $H$. For a graph or directed graph, let $\mathcal{M}$ denote the family of maximal matchings, and let…

Let $B=F_{2,3}$ be the bowtie graph, with a distinguished center vertex, and let $\vec{B}$ be an orientation of $B$ having exactly three edges directed toward the center vertex or…

Let $B=F_{2,3}$ be the bowtie graph, with a distinguished center vertex. Let $G$ be a complete tripartite graph with part sizes $1$, $\left\lfloor\frac{n-1}{2}\right\rfloor$, and…

The 6-edge-connectivity conjecture. Every 6-edge-connected graph has a strongly connected modulo $3$-orientation.

Let $H=(V,\mathcal E)$ be a $\tau$-uniform hypergraph. For $X\subset V$, let $d_H(X)$ be the sum of $|X\cap E|$ over all hyperedges $E\in\mathcal E$ separated by $X$, meaning…