42 problems

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…

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

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…

Conjecture on $m(n,d)$.

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…

Let $g\in\mathbb{N}$. A graph has the AOP property if it admits an acyclic orientation with at most one directed path between any pair of vertices, and its girth is the length of i…

Let $G$ be a graph, let $\vec{G}$ be an orientation of $G$, and let $tac(\vec{G})$ denote its total arc-connectivity. An orientation maximizes total arc-connectivity when it maximi…