http://openproblemgarden.org/op/partial_list_coloring_0 Comments for "Partial List Coloring" en http://openproblemgarden.org/op/partial_list_coloring_0 <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/iradmusa_moharram">Iradmusa</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> <p>Let <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> be a simple graph, and for every list assignment <img class="teximage" src="/files/tex/a2c0112ede57f2f125c3f8fdccdb8c672e612947.png" alt="$ \mathcal{L} $" /> let <img class="teximage" src="/files/tex/b2053a5ea4c77171bcd3f700d180b6c9aecb9481.png" alt="$ \lambda_{\mathcal{L}} $" /> be the maximum number of vertices of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> which are colorable with respect to <img class="teximage" src="/files/tex/a2c0112ede57f2f125c3f8fdccdb8c672e612947.png" alt="$ \mathcal{L} $" />. Define <img class="teximage" src="/files/tex/76f80603b406338324c7584192f8966d319cbc4c.png" alt="$ \lambda_t = \min{ \lambda_{\mathcal{L}} } $" />, where the minimum is taken over all list assignments <img class="teximage" src="/files/tex/a2c0112ede57f2f125c3f8fdccdb8c672e612947.png" alt="$ \mathcal{L} $" /> with <img class="teximage" src="/files/tex/df1b046a00ac652a380ec500c6bdc1aa522c9da0.png" alt="$ |\mathcal{L}| = t $" /> for all <img class="teximage" src="/files/tex/1466419f1101030390df1795c6f6a568ac18776b.png" alt="$ v \in V(G) $" />. </p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; [2] Let <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> be a graph with list chromatic number <img class="teximage" src="/files/tex/46e2d5b6cf87b7e24d9ac72345043107b7ccae3a.png" alt="$ \chi_\ell $" /> and <img class="teximage" src="/files/tex/a3fc6cd4c98fabb35869474a493492a0435792e7.png" alt="$ 1\leq r\leq s\leq \chi_\ell $" />. Then <img class="teximage" src="/files/tex/47be18e956355dd433b88b66eabf01a9e3ed5f61.png" alt="\[\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.\]" /> </div> </tr></td> </table> </td> </tr> </table> Iradmusa, Moharram list assignment list coloring Graph Theory Coloring Vertex coloring http://openproblemgarden.org/op/partial_list_coloring_0#comment Mon, 12 May 2008 18:31:28 +0200 Iradmusa 788 at http://openproblemgarden.org