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
Combinatorics

2-accessibility of primes ★★

Author(s): Landman; Robertson

Question   Is the set of prime numbers 2-accessible?

Keywords: monochromatic diffsequences; primes

Posted by vjungic
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