Home » Keyword index

digraph


Graph Theory » Directed Graphs » Tournaments

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

Keywords: digraph; edge-coloring; tournament

Posted by mdevos
updated July 15th, 2008
add new comment
Graph Theory » Directed Graphs » Tournaments

Monochromatic reachability in edge-colored tournaments ★★★

Author(s): Erdos

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

Keywords: digraph; edge-coloring; tournament

Posted by mdevos
updated July 9th, 2008
add new comment
Graph Theory » Directed Graphs

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 feedback edge set.

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

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

Posted by mdevos
updated July 8th, 2008
add new comment
Graph Theory » Infinite Graphs

Highly arc transitive two ended digraphs ★★

Author(s): Cameron; Praeger; Wormald

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.

Keywords: arc transitive; digraph; infinite graph

Posted by mdevos
updated October 29th, 2007
add new comment
Graph Theory » Infinite Graphs

Universal highly arc transitive digraphs ★★★

Author(s): Cameron; Praeger; Wormald

An 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 universal if for every pair of edges $ e,f $, there is an alternating walk containing both $ e $ and $ f $

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

Keywords: arc transitive; digraph

Posted by mdevos
updated October 21st, 2007
add new comment
Graph Theory » Directed Graphs

Woodall's Conjecture ★★★

Author(s): Woodall

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

Keywords: digraph; packing

Posted by mdevos
updated April 5th, 2007
add new comment
Graph Theory » Directed Graphs

The Two Color Conjecture ★★

Author(s): Neumann-Lara

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

Keywords: acyclic; digraph; planar

Posted by mdevos
updated May 31st, 2007
1 comment
Syndicate content