http://openproblemgarden.org/op/partial_list_coloring Comments for "Partial List Coloring" en http://openproblemgarden.org/op/partial_list_coloring <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/albertson_michael_o">Albertson</a>; <a href="/category/grossman_sara">Grossman</a>; <a href="/category/haas_ruth">Haas</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/coloring">Coloring</a> » <a href="/category/vertex_coloring">Vertex 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; Let <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> be a simple graph with <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" /> vertices and list chromatic number <img class="teximage" src="/files/tex/b68082745a25a09294e2c92c006b61d3ef1a9e54.png" alt="$ \chi_\ell(G) $" />. Suppose that <img class="teximage" src="/files/tex/1aee119babfe25de435c7cf6beff3114a5ae9326.png" alt="$ 0\leq t\leq \chi_\ell $" /> and each vertex of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is assigned a list of <img class="teximage" src="/files/tex/4761b031c89840e8cd2cda5b53fbc90c308530f3.png" alt="$ t $" /> colors. Then at least <img class="teximage" src="/files/tex/59b72b19d6799e1fd7a0fc093bff9283068dc838.png" alt="$ \frac{tn}{\chi_\ell(G)} $" /> vertices of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> can be colored from these lists. </div> </tr></td> </table> </td> </tr> </table> Albertson, Michael O. Grossman, Sara Haas, Ruth list assignment list coloring Graph Theory Coloring Vertex coloring http://openproblemgarden.org/op/partial_list_coloring#comment Mon, 05 May 2008 16:22:10 +0200 Iradmusa 771 at http://openproblemgarden.org