http://openproblemgarden.org/op/pentagon_problem Comments for "Pentagon problem" en http://openproblemgarden.org/op/pentagon_problem <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/nesetril">Nesetril</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/coloring">Coloring</a> » <a href="/category/homomorphisms">Homomorphisms</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Question</b>&nbsp;&nbsp; Let <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> be a 3-regular graph that contains no cycle of length shorter than <img class="teximage" src="/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png" alt="$ g $" />. Is it true that for large enough~<img class="teximage" src="/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png" alt="$ g $" /> there is a <a href="http://en.wikipedia.org/wiki/graph_homomorphism">homomorphism</a> <img class="teximage" src="/files/tex/090efbbd450a0134afde46b53f2dbe35011946d1.png" alt="$ G \to C_5 $" />? </div> </tr></td> </table> </td> </tr> </table> Nesetril, Jaroslav cubic homomorphism Graph Theory Coloring Homomorphisms http://openproblemgarden.org/op/pentagon_problem#comment Sat, 24 Mar 2007 03:20:09 +0100 Robert Samal 167 at http://openproblemgarden.org