http://openproblemgarden.org/op/linial_berge_path_partition_duality Comments for "Linial-Berge path partition duality" en http://openproblemgarden.org/op/linial_berge_path_partition_duality#comment-217 <p>Thanks much for the correction, I've updated the problem.</p> Wed, 19 Sep 2007 20:20:34 +0200 mdevos comment 217 at http://openproblemgarden.org http://openproblemgarden.org/op/linial_berge_path_partition_duality#comment-216 <p>There is a typo in the formulation : </p> <p>Replace "maximum k-norm" by "minimum k-norm". </p> <p>Thanks ! Best, Andras Sebo </p> Wed, 19 Sep 2007 19:19:46 +0200 Anonymous comment 216 at http://openproblemgarden.org http://openproblemgarden.org/op/linial_berge_path_partition_duality <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/berge">Berge</a>; <a href="/category/linial">Linial</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/coloring">Coloring</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; The minimum <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" />-norm of a path partition on a directed graph <img class="teximage" src="/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png" alt="$ D $" /> is no more than the maximal size of an induced <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" />-colorable subgraph. </div> </tr></td> </table> </td> </tr> </table> Berge, Claude Linial, Nathan coloring directed path partition Graph Theory Coloring http://openproblemgarden.org/op/linial_berge_path_partition_duality#comment Tue, 27 Mar 2007 13:30:55 +0200 berger 170 at http://openproblemgarden.org