42 problems

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…

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 $\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=(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…

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…

Conjecture on $m(n,d)$.

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

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…

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…

Let $G$ be a bridgeless graph of order $n$ and minimum degree $\delta\geq 2$, and let $\overrightarrow{\operatorname{diam}}(G)$ denote the minimum diameter over all strongly connec…

Let $G$ be a loopless graph, and let $d(v)$ denote the degree of each vertex $v\in V(G)$. Given a function $F:V(G)\to 2^{\mathbb N}$, an orientation is $F$-avoiding if its out-degr…

Let $G$ be a loopless $d$-regular graph, with parallel edges permitted, and let $F\subseteq\{0,1,\ldots,d\}$ be a list of forbidden out-degrees. An orientation is $F$-avoiding if n…

Conjecture for distinguishing index two. If

Lower-bound conjecture.

Anti-Sidorenko orientations conjecture for trees. For every undirected tree, there exists some orientation that has the tournament anti-Sidorenko property. The paper says that this…

Chudnovsky–Edwards–Kim–Scott–Seymour conjecture. There exists an orientation $D$ of $G$ such that $\delta_D^+(U)$ and $\delta_D^-(U)$ are both nonempty for every…

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