Importance: Medium ✭✭
Recomm. for undergrads: no
Posted by: mdevos
on: June 20th, 2007
Problem   Does every triangle-free planar graph of maximum degree three have circular chromatic number at most $ \frac{20}{7} $?

Throughout, we let $ \chi_c(G) $ denote the circular chromatic number of the graph $ G $.

A well-known Question of Nesetril asks if $ \chi_c(G) \le \frac{5}{2} $ for all cubic graphs $ G $ of sufficiently high girth. A conjecture of Jaeger asserts that $ \chi_c(G) \le 2 + \frac{1}{k} $ for every planar graph $ G $ of girth $ 4k+1 $. There are numerous partial results on these problems, and there are many interesting questions concerning the circular chromatic numbers of restricted families of graphs. Here we are restricted to planar graphs of girth $ \ge 4 $ with maximum degree $ \le 3 $. The dodecahedron lives in this class and has $ \chi_c = \frac{20}{7} $. It remains unclear if anyone else in this class might have $ \chi_c $ larger.

A related conjecture of X. Zhu asserts that for every triangle-free planar graph $ G $ with $ \Delta(G)\le 4 $ and $ |V(G)|<3k $ one has $ \chi_c(G)\le 3-1/k $.


* indicates original appearance(s) of problem.


Comments are limited to a maximum of 1000 characters.
More information about formatting options