http://openproblemgarden.org/op/monochromatic_reachability_vs_rainbow_triangles Comments for "Monochromatic reachability or rainbow triangles" en http://openproblemgarden.org/op/monochromatic_reachability_vs_rainbow_triangles <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/sands_bill">Sands</a>; <a href="/category/sauer_norbert_w">Sauer</a>; <a href="/category/woodrow_robert_e">Woodrow</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/directed_graphs">Directed Graphs</a> » <a href="/category/tournaments">Tournaments</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>In an edge-colored digraph, we say that a subgraph is <em>rainbow</em> if all its edges have distinct colors, and <em>monochromatic</em> if all its edges have the same color. </p> <div class="envtheorem"><b>Problem</b>&nbsp;&nbsp; Let <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> be a tournament with edges colored from a set of three colors. Is it true that <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> must have either a rainbow directed cycle of length three or a vertex <img class="teximage" src="/files/tex/96cbd9a16c6a5eab03815b093b08f3b2db614e9a.png" alt="$ v $" /> so that every other vertex can be reached from <img class="teximage" src="/files/tex/96cbd9a16c6a5eab03815b093b08f3b2db614e9a.png" alt="$ v $" /> by a monochromatic (directed) path? </div> </tr></td> </table> </td> </tr> </table> Sands, Bill Sauer, Norbert W. Woodrow, Robert E. digraph edge-coloring tournament Graph Theory Directed Graphs Tournaments http://openproblemgarden.org/op/monochromatic_reachability_vs_rainbow_triangles#comment Tue, 15 Jul 2008 07:56:08 +0200 mdevos 1808 at http://openproblemgarden.org