Let p be a positive real number and S(p) the circle in the plane with circumference p. A subset U of S(p) is said to be assignable if it is the union of finitely many open arcs on S(p). Let length(U) denote the length of U. If G is a graph, a function L that assigns to each vertex v of G an assignable subset L(v) of S(p) is called a list assignment. An L-coloring of G is a function c from V(G) to S(p) such that c(v) is an element of L(v) for each vertex v of G and such that for every pair u, v of adjacent vertices of G, the distance between c(u) and c(v) on S(p) is at least 1.
The graph G is circularly t-choosable if for every p and every list assignment L in S(p) with length(L(v)) greater or equal to t for every vertex v, there exists an L-coloring of G.
There are many questions that one can ask about circular choosability. Let us mention some of them:
Problem 1: Is it true that a graph with list chromatic number k is circularly k-choosable?
Problem 2: If G is a graph with maximum vertex degree D, is the line graph of G circularly (D+1)-choosable?
Problem 3: Which cubic graphs are circularly t-choosable for some t that is smaller than 4?
Problem 4: What is the smallest real number t such that every planar graph is circularly t-choosable?
Most likely, the answer to Problem 4 is between 4 and 5.
Send comments to Bojan.Mohar@uni-lj.si