Circular choosability of planar graphs
Status open medium confidence
As of the posting date (August 2012), the best known bounds on $\tau = \sup\{\mathrm{cch}(G) : G \text{ planar}\}$ were $6 \le \tau \le 8$, established by Havet, Kang, Müller, and Sereni (2009). Exhaustive searching across arXiv, journal indices, and web resources found no verifiable post-2012 paper that narrows this gap or resolves the problem for general planar graphs.
Reviewer notes. The Wang–Liu paper on circular choosability of planar graphs with large girth appeared on the Combinatorial Press page and ResearchGate, but its publication date is 2011, predating the OPG posting, so it is not included in since_posted. The HAL Inria page for the HKMS paper returned HTTP 403 and could not be verified; however, the 2009 HKMS result is pre-posting baseline knowledge and requires no citation here. No arXiv preprint or journal paper post-August 2012 specifically addressing the $6$–$8$ gap for circular choosability of general planar graphs was found through any of the six queries. Confidence is medium rather than high because the topic is niche enough that relevant papers could reside in journals (e.g., Ars Combinatoria, Australasian J. Combinatorics) not well indexed by the search engine.
Discussion
The problem was first posed in 2003 by Mohar (Problem 4 of link *) who suggested the answer should be between 4 and 5. Some time later, Havet, Kang, Müller, and Sereni [HKMS] showed that in fact the answer is somewhere between 6 and 8. The upper bound extends a celebrated planar choosability proof due to Thomassen [T]. The lower bound is by way of an elementary, though rather large, construction.
Bibliography
-
[HKMS]F. Havet, R. J. Kang, T. Müller, and J.-S. Sereni. Circular choosability. J. Graph Theory 61 (2009), no. 4, 241--270. -
[T]C. Thomassen. Every planar graph is 5-choosable. J. Combinatorial Theory B 62 (1994) 180--181