Circular choosability via combinatorial Nullstellensatz

AbstractA 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