Circular choosability

Suppose L is a list assignment which assigns to each vertex x a set L(x) of nonnegative integers as a permissible colours. An L-(p,q)-colouring of G (where p > max L(x) for all x) is a (p,q) colouring f of G such that f(x) \in L(x) for each x.  Suppose  l: V(G) \to {0,1, ..., p} assigns to each vertex a nonnegative integer not greater than p. We say G is l-(p,q)-choosable if for any list assignment L with |L(x)|=l(x), G has an L-(p,q)-colouring. The following results are proved in [RZ]:

Theorem A: If G is a tree, then G is l-(p,q)-choosable if and only if for any subtree T,

                    \sum_{x \in V(T)} l(x) \ge 2|E(T)| q+1.

¡@

Theorem B: If G is a cycle of length n \ge 2k+1, then G is l-(2k+1,k)-choosable if for every subgraph H of G,

                    \sum_{x \in V(H)} l(x) \ge 2|E(H)| k+1.

Question 1: Does Theorem B remain true of G is a theta graph? (A theta \theta_{a,b,c} consists of three paths joining x and y such that the paths are internally vertex-disjoint and are of lengths a,b,c respectively.)

We say a graph G is circular t-choosable if G is l-(p,q)-choosable whenever l(x) \ge tq for each x.  The circular choosability of G (or the circular list chromatic number of G) is

\chi_{c,l}(G) = inf { t:  G is circular t-choosable }

Let \chi_l(G) be the choosability of G. It is known [Zhu05] for any graph G, \chi_{c,l}(G) \ge \chi_l(G)-1, and for any \epsilon > 0, there are graphs G for which \chi_{c,l}(G) > (2-\epsilon) \chi_l(G). 

Question 2: Does there exist a real number s such that for any graph G,

                   \chi_{c,l}(G) \le s \chi_l(G) ?

If such a real number exists, then s is at least 2.

Question 3: Is it true that  for any graph G,

                   \chi_{c,l}(G) \le 2 \chi_l(G) ?

Conjecture 1: Every 2-choosable graph is circular 2-choosable.

To prove a Conjecture  1, it suffices to show that \theta_{2,2,2n} is circular 2-choosable for any positive integer n. It is proved in [NWZ] that \theta_{2,2,2n} have circular choosability at most      

2(2n+4)/(2n+3).

              

¡@

¡@