digraph


Monochromatic reachability or rainbow triangles ★★★

Author(s): Sands; Sauer; Woodrow

In an edge-colored digraph, we say that a subgraph is \emph{rainbow} if all its edges have distinct colors, and \emph{monochromatic} if all its edges have the same color.

\begin{problem} Let $G$ be a tournament with edges colored from a set of three colors. Is it true that $G$ must have either a rainbow directed cycle of length three or a vertex $v$ so that every other vertex can be reached from $v$ by a monochromatic (directed) path? \end{problem}

Keywords: digraph; edge-coloring; tournament

Monochromatic reachability in edge-colored tournaments ★★★

Author(s): Erdos

\begin{problem} For every $n$, is there a (least) positive integer $f(n)$ so that whenever a tournament has its edges colored with $n$ colors, there exists a set $S$ of at most $f(n)$ vertices so that every vertex has a monochromatic path to some point in $S$? \end{problem}

Keywords: digraph; edge-coloring; tournament

Non-edges vs. feedback edge sets in digraphs ★★★

Author(s): Chudnovsky; Seymour; Sullivan

For any simple digraph $G$, we let $\gamma(G)$ be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and $\beta(G)$ be the size of the smallest \Def[feedback edge set]{feedback arc set}.

\begin{conjecture}If $G$ is a simple digraph without directed cycles of length $\le 3$, then $\beta(G) \le \frac{1}{2} \gamma(G)$. \end{conjecture}

Keywords: acyclic; digraph; feedback edge set; triangle free

Highly arc transitive two ended digraphs ★★

Author(s): Cameron; Praeger; Wormald

\begin{conjecture} If $G$ is a highly arc transitive digraph with two ends, then every tile of $G$ is a disjoint union of complete bipartite graphs. \end{conjecture}

Keywords: arc transitive; digraph; infinite graph

Universal highly arc transitive digraphs ★★★

Author(s): Cameron; Praeger; Wormald

An \emph{alternating} walk in a digraph is a walk $v_0,e_1,v_1,\ldots,v_m$ so that the vertex $v_i$ is either the head of both $e_i$ and $e_{i+1}$ or the tail of both $e_i$ and $e_{i+1}$ for every $1 \le i \le m-1$. A digraph is \emph{universal} if for every pair of edges $e,f$, there is an alternating walk containing both $e$ and $f$

\begin{question} Does there exist a locally finite highly arc transitive digraph which is universal? \end{question}

Keywords: arc transitive; digraph

Woodall's Conjecture ★★★

Author(s): Woodall

\begin{conjecture} If $G$ is a directed graph with smallest directed cut of size $k$, then $G$ has $k$ disjoint dijoins. \end{conjecture}

Keywords: digraph; packing

The Two Color Conjecture ★★

Author(s): Neumann-Lara

\begin{conjecture} If $G$ is an orientation of a simple planar graph, then there is a partition of $V(G)$ into $\{X_1,X_2\}$ so that the graph induced by $X_i$ is acyclic for $i=1,2$. \end{conjecture}

Keywords: acyclic; digraph; planar

Syndicate content