http://openproblemgarden.org/op/unfriendly_partitions Comments for "Unfriendly partitions" en http://openproblemgarden.org/op/unfriendly_partitions <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/cowan_r">Cowan</a>; <a href="/category/emerson_w">Emerson</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/infinite_graphs">Infinite Graphs</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>If <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is a graph, we say that a partition of <img class="teximage" src="/files/tex/b324b54d8674fa66eb7e616b03c7a601ccdab6b8.png" alt="$ V(G) $" /> is <em>unfriendly</em> if every vertex has at least as many neighbors in the other classes as in its own. </p> <div class="envtheorem"><b>Problem</b>&nbsp;&nbsp; Does every countably infinite graph have an unfriendly partition into two sets? </div> </tr></td> </table> </td> </tr> </table> Cowan, Robert H. Emerson, William R. coloring infinite graph partition Graph Theory Infinite Graphs http://openproblemgarden.org/op/unfriendly_partitions#comment Mon, 22 Oct 2007 02:39:11 +0200 mdevos 687 at http://openproblemgarden.org