![](/files/happy5.png)
Woodrow, Robert E.
Monochromatic reachability in arc-colored digraphs ★★★
Author(s): Sands; Sauer; Woodrow
Conjecture For every
, there exists an integer
such that if
is a digraph whose arcs are colored with
colors, then
has a
set which is the union of
stables sets so that every vertex has a monochromatic path to some vertex in
.
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ f(k) $](/files/tex/e055b3867e7cb3cc4b2f50739eedda7657999214.png)
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ S $](/files/tex/d2b76a0ee5465d3e3ecc846c8e3d632edd8b2bbf.png)
![$ f(k) $](/files/tex/e055b3867e7cb3cc4b2f50739eedda7657999214.png)
![$ S $](/files/tex/d2b76a0ee5465d3e3ecc846c8e3d632edd8b2bbf.png)
Keywords:
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?
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ v $](/files/tex/96cbd9a16c6a5eab03815b093b08f3b2db614e9a.png)
![$ v $](/files/tex/96cbd9a16c6a5eab03815b093b08f3b2db614e9a.png)
Keywords: digraph; edge-coloring; tournament
![Syndicate content Syndicate content](/misc/feed.png)