# digraph

## Monochromatic reachability or rainbow triangles ★★★

Author(s): Sands; Sauer; Woodrow

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

Problem   Let be a tournament with edges colored from a set of three colors. Is it true that must have either a rainbow directed cycle of length three or a vertex so that every other vertex can be reached from by a monochromatic (directed) path?

Keywords: digraph; edge-coloring; tournament

## Monochromatic reachability in edge-colored tournaments ★★★

Author(s): Erdos

Problem   For every , is there a (least) positive integer so that whenever a tournament has its edges colored with colors, there exists a set of at most vertices so that every vertex has a monochromatic path to some point in ?

Keywords: digraph; edge-coloring; tournament

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

Author(s): Chudnovsky; Seymour; Sullivan

For any simple digraph , we let be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and be the size of the smallest feedback edge set.

Conjecture  If is a simple digraph without directed cycles of length , then .

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

## Highly arc transitive two ended digraphs ★★

Author(s): Cameron; Praeger; Wormald

Conjecture   If is a highly arc transitive digraph with two ends, then every tile of is a disjoint union of complete bipartite graphs.

Keywords: arc transitive; digraph; infinite graph

## Universal highly arc transitive digraphs ★★★

Author(s): Cameron; Praeger; Wormald

An alternating walk in a digraph is a walk so that the vertex is either the head of both and or the tail of both and for every . A digraph is universal if for every pair of edges , there is an alternating walk containing both and

Question   Does there exist a locally finite highly arc transitive digraph which is universal?

Keywords: arc transitive; digraph

## Woodall's Conjecture ★★★

Author(s): Woodall

Conjecture   If is a directed graph with smallest directed cut of size , then has disjoint dijoins.

Keywords: digraph; packing

## The Two Color Conjecture ★★

Author(s): Neumann-Lara

Conjecture   If is an orientation of a simple planar graph, then there is a partition of into so that the graph induced by is acyclic for .

Keywords: acyclic; digraph; planar