http://openproblemgarden.org/op/friendly_partitions Comments for "Friendly partitions" en http://openproblemgarden.org/op/friendly_partitions#comment-93647 <p>In the bibliography, this is known as Satisfactory graph partition or Internal graph partition.</p> Wed, 05 Aug 2020 00:55:20 +0200 Anonymous comment 93647 at http://openproblemgarden.org http://openproblemgarden.org/op/friendly_partitions <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/devos">DeVos</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/basic_graph_theory">Basic G.T.</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>A <em>friendly</em> partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.</p> <div class="envtheorem"><b>Problem</b>&nbsp;&nbsp; Is it true that for every <img class="teximage" src="/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png" alt="$ r $" />, all but finitely many <img class="teximage" src="/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png" alt="$ r $" />-regular graphs have friendly partitions? </div> </tr></td> </table> </td> </tr> </table> DeVos, Matt edge-cut partition regular Graph Theory Basic Graph Theory http://openproblemgarden.org/op/friendly_partitions#comment Sun, 08 Nov 2009 09:51:29 +0100 mdevos 37163 at http://openproblemgarden.org