http://openproblemgarden.org/op/algorithm_for_graph_homomorphisms Comments for "Algorithm for graph homomorphisms" en http://openproblemgarden.org/op/algorithm_for_graph_homomorphisms <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/fomin_fedor_v">Fomin</a>; <a href="/category/heggernes_pinar">Heggernes</a>; <a href="/category/kratsch_dieter">Kratsch</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;</p> <p>Is there an algorithm that decides, for input graphs <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> and <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" />, whether there exists a homomorphism from <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> to <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" /> in time <img class="teximage" src="/files/tex/5e224f330363a25ad4afca48ded68b285315655e.png" alt="$ O(c^{|V(G)|+|V(H)|}) $" /> for some constant <img class="teximage" src="/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png" alt="$ c $" />? </div> </tr></td> </table> </td> </tr> </table> Fomin, Fedor V. Heggernes, Pinar Kratsch, Dieter algorithm Exponential-time algorithm homomorphism Graph Theory Coloring Homomorphisms http://openproblemgarden.org/op/algorithm_for_graph_homomorphisms#comment Thu, 08 Jul 2010 14:15:23 +0200 jfoniok 37232 at http://openproblemgarden.org