http://openproblemgarden.org/op/complexity_of_the_h_factor_problem Comments for "Complexity of the H-factor problem." en http://openproblemgarden.org/op/complexity_of_the_h_factor_problem <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/kuhn_daniella">Kühn</a>; <a href="/category/osthus_deryk">Osthus</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/extremal_graph_theory">Extremal G.T.</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>An <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" />-factor in a graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is a set of vertex-disjoint copies of <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" /> covering all vertices of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />.<br /> <div class="envtheorem"><b>Problem</b>&nbsp;&nbsp;Let <img class="teximage" src="/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png" alt="$ c $" /> be a fixed positive real number and <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" /> a fixed graph. Is it NP-hard to determine whether a graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> on <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" /> vertices and minimum degree <img class="teximage" src="/files/tex/d86cd3be7381a5c384b9e02ce96029e79af296a1.png" alt="$ cn $" /> contains and <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" />-factor?</p> </div> </tr></td> </table> </td> </tr> </table> Kühn, Daniella Osthus, Deryk Graph Theory Extremal Graph Theory http://openproblemgarden.org/op/complexity_of_the_h_factor_problem#comment Tue, 05 Mar 2013 09:23:26 +0100 fhavet 46738 at http://openproblemgarden.org