Circular choosability via combinatorial Nullstellensatz

✍ Scribed by Serguei Norine; Tsai-Lien Wong; Xuding Zhu

• Publisher: John Wiley and Sons
• Year: 2008
• Tongue: English
• Weight: 169 KB
• Volume: 59
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20333

✦ Synopsis

Abstract

A p‐list assignment L of a graph G assigns to each vertex v of G a set ${{L}}({{v}})\subseteq {{{0}}{{,}} {{1}}{{,}}\ldots{{,}}, {{p}}-{{1}}}$ of permissible colors. We say G is L‐(P, q)‐colorable if G has a (P, q)‐coloring h such that h(v) ϵ L(v) for each vertex v. The circular list chromatic number $\chi_{{{c}}{{,}}{{l}}}({{G}})$ of a graph G is the infimum of those real numbers t for which the following holds: For any P, q, for any P‐list assignment L with $|{{L}}({{v}})| \geq {{tq}}$, G is L‐(P, q)‐colorable. We prove that if G has an orientation D which has no odd directed cycles, and L is a P‐list assignment of G such that for each vertex v, $|{{L}}({{v}})| = {{d}}^+_{{D}}({{v}})({{2}}{{q}}-{{1}})+{{1}}$, then G is L‐(P, q)‐colorable. This implies that if G is a bipartite graph, then $\chi_{{{c}}{{,}}{{l}}}({{G}})\leq {{2}}\lceil {{mad}}({{G}})/{{2}}\rceil$, where ${{\rm mad}}({{G}})$ is the maximum average degree of a subgraph of G. We further prove that if G is a connected bipartite graph which is not a tree, then $\chi_{{{c}}{{,}}{{l}}}({{G}})\leq { {mad}}({{G}})$. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 190–204, 2008