http://openproblemgarden.org/op/circular_choosability_of_planar_graphs Comments for "Circular choosability of planar graphs" en http://openproblemgarden.org/op/circular_choosability_of_planar_graphs <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/mohar">Mohar</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/homomorphisms">Homomorphisms</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>Let <img class="teximage" src="/files/tex/84d27ab6917a72564d175c385c748c9a65380540.png" alt="$ G = (V, E) $" /> be a graph. If <img class="teximage" src="/files/tex/928cd9d544fdea62f88a627aaee28c416c4366c0.png" alt="$ p $" /> and <img class="teximage" src="/files/tex/0f3b87f25409a259a157fcac9808cafa54efa0c7.png" alt="$ q $" /> are two integers, a <img class="teximage" src="/files/tex/5fdfd6d4364192fb4fdca04319ffa276d7272185.png" alt="$ (p,q) $" />-colouring of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is a function <img class="teximage" src="/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png" alt="$ c $" /> from <img class="teximage" src="/files/tex/517af4139f21bb21424f7896561555919bc4678a.png" alt="$ V $" /> to <img class="teximage" src="/files/tex/f5c860fcb7a5a6dfc6f35a952b277fef29120497.png" alt="$ \{0,\dots,p-1\} $" /> such that <img class="teximage" src="/files/tex/81255083ce9b5d54b8c117919431b505eac7d3e3.png" alt="$ q \le |c(u)-c(v)| \le p-q $" /> for each edge <img class="teximage" src="/files/tex/e9f05d495dc81a1f85e51fee85691e91dd500243.png" alt="$ uv\in E $" />. Given a list assignment <img class="teximage" src="/files/tex/73f33398d7e8aa42e6ec25ee2bb4f2b57ed3391a.png" alt="$ L $" /> of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />, i.e.~a mapping that assigns to every vertex <img class="teximage" src="/files/tex/96cbd9a16c6a5eab03815b093b08f3b2db614e9a.png" alt="$ v $" /> a set of non-negative integers, an <img class="teximage" src="/files/tex/73f33398d7e8aa42e6ec25ee2bb4f2b57ed3391a.png" alt="$ L $" />-colouring of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is a mapping <img class="teximage" src="/files/tex/ae1eeae9f205485b3b1d97109a792b4dc7ec218a.png" alt="$ c : V \to N $" /> such that <img class="teximage" src="/files/tex/ee3e9115f72b68747b9ac848930cf8a1bce9b141.png" alt="$ c(v)\in L(v) $" /> for every <img class="teximage" src="/files/tex/c4288e8e158f9ae52ceb4bc3033583494673aa7f.png" alt="$ v\in V $" />. A list assignment <img class="teximage" src="/files/tex/73f33398d7e8aa42e6ec25ee2bb4f2b57ed3391a.png" alt="$ L $" /> is a <img class="teximage" src="/files/tex/4761b031c89840e8cd2cda5b53fbc90c308530f3.png" alt="$ t $" />-<img class="teximage" src="/files/tex/5fdfd6d4364192fb4fdca04319ffa276d7272185.png" alt="$ (p,q) $" />-list-assignment if <img class="teximage" src="/files/tex/edbf80101dd57bc27ae9f8f75d01cecb65b85b60.png" alt="$ L(v) \subseteq \{0,\dots,p-1\} $" /> and <img class="teximage" src="/files/tex/11c7f862935b0cb68fb051793eb9938bcac262f1.png" alt="$ |L(v)| \ge tq $" /> for each vertex <img class="teximage" src="/files/tex/18255450ec5c0f06f7a4d8b5f1c60e5a77f6d5d9.png" alt="$ v \in V $" /> . Given such a list assignment <img class="teximage" src="/files/tex/73f33398d7e8aa42e6ec25ee2bb4f2b57ed3391a.png" alt="$ L $" />, the graph G is <img class="teximage" src="/files/tex/5fdfd6d4364192fb4fdca04319ffa276d7272185.png" alt="$ (p,q) $" />-<img class="teximage" src="/files/tex/73f33398d7e8aa42e6ec25ee2bb4f2b57ed3391a.png" alt="$ L $" />-colourable if there exists a <img class="teximage" src="/files/tex/5fdfd6d4364192fb4fdca04319ffa276d7272185.png" alt="$ (p,q) $" />-<img class="teximage" src="/files/tex/73f33398d7e8aa42e6ec25ee2bb4f2b57ed3391a.png" alt="$ L $" />-colouring <img class="teximage" src="/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png" alt="$ c $" />, i.e. <img class="teximage" src="/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png" alt="$ c $" /> is both a <img class="teximage" src="/files/tex/5fdfd6d4364192fb4fdca04319ffa276d7272185.png" alt="$ (p,q) $" />-colouring and an <img class="teximage" src="/files/tex/73f33398d7e8aa42e6ec25ee2bb4f2b57ed3391a.png" alt="$ L $" />-colouring. For any real number <img class="teximage" src="/files/tex/b9b71fe1446a60666050951b891ed6f44c97682f.png" alt="$ t \ge 1 $" />, the graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is <img class="teximage" src="/files/tex/4761b031c89840e8cd2cda5b53fbc90c308530f3.png" alt="$ t $" />-<img class="teximage" src="/files/tex/5fdfd6d4364192fb4fdca04319ffa276d7272185.png" alt="$ (p,q) $" />-choosable if it is <img class="teximage" src="/files/tex/5fdfd6d4364192fb4fdca04319ffa276d7272185.png" alt="$ (p,q) $" />-<img class="teximage" src="/files/tex/73f33398d7e8aa42e6ec25ee2bb4f2b57ed3391a.png" alt="$ L $" />-colourable for every <img class="teximage" src="/files/tex/4761b031c89840e8cd2cda5b53fbc90c308530f3.png" alt="$ t $" />-<img class="teximage" src="/files/tex/5fdfd6d4364192fb4fdca04319ffa276d7272185.png" alt="$ (p,q) $" />-list-assignment <img class="teximage" src="/files/tex/73f33398d7e8aa42e6ec25ee2bb4f2b57ed3391a.png" alt="$ L $" />. Last, <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is circularly <img class="teximage" src="/files/tex/4761b031c89840e8cd2cda5b53fbc90c308530f3.png" alt="$ t $" />-choosable if it is <img class="teximage" src="/files/tex/4761b031c89840e8cd2cda5b53fbc90c308530f3.png" alt="$ t $" />-<img class="teximage" src="/files/tex/5fdfd6d4364192fb4fdca04319ffa276d7272185.png" alt="$ (p,q) $" />-choosable for any <img class="teximage" src="/files/tex/928cd9d544fdea62f88a627aaee28c416c4366c0.png" alt="$ p $" />, <img class="teximage" src="/files/tex/0f3b87f25409a259a157fcac9808cafa54efa0c7.png" alt="$ q $" />. The circular choosability (or circular list chromatic number or circular choice number) of G is <img class="teximage" src="/files/tex/16c6e894f9ec46560b0db0bc73ce3e293727dc96.png" alt="$$cch(G) := \inf\{t \ge 1 : G \text{ is circularly $t$-choosable}\}.$$" /></p> <div class="envtheorem"><b>Problem</b>&nbsp;&nbsp; What is the best upper bound on circular choosability for planar graphs? </div> </tr></td> </table> </td> </tr> </table> Mohar, Bojan choosability circular colouring planar graphs Graph Theory Coloring Homomorphisms http://openproblemgarden.org/op/circular_choosability_of_planar_graphs#comment Thu, 23 Aug 2012 16:55:45 +0200 rosskang 37619 at http://openproblemgarden.org