Open Problem Garden

Importance: Medium ✭✭

Author(s):	Ghebleh, Mohammad
	Zhu, Xuding

Subject:	Graph Theory
	» Coloring
	» » Vertex coloring

Keywords:	circular coloring
	planar graph
	triangle free

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$ .