# 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.

## 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 .