Chi_c of triangle free planar graphs of maximum degree 3 or 4

Question: What is the maximum circular chromatic number of a triangle free planar graphs of maximum degree  3 ?

Presently, the known maximum is 20/7,  which is the circular chromatic number of the  dodecahedron. I guess this is the maximum value one can get.

Conjecture: If G is a triangle free planar graph of maximum degree 3, then chi_c(G) <= 20/7.

For the fractional chromatic number of triangle free planar graphs of maximum degree 3, the following conjecture is proposed by Heckman and Thomas [HR2].

Conjecture[Heckman and Thomas] If G is triangle free planar graphs of maximum degree  3, then chi_f(G) <= 8/3.

If the condition of planar graph is dropped, then Petersen graph is cubic, triangle free and has \chi_c(G) = 3. For fractional chromatic number,   Heckman and Thomas [HR2] have the following conjecture:

Conjecture[Heckman and Thomas]: If G is a triangle free graph of maximum degree 3, then chi_f(G) <= 14/5.

There are triangle free planar graphs with circular chromatic number 3 (which is the maximum by Grotzsch theorem). However, all known finite triangle free planar graphs G with chi_c(G) = 3 has maximum degree at least 5.

Question: Is there a finite triangle free planar graph G of maximum degree 4 such that chi_c(G) = 3 ?

Theorem 1: For each integer k>= 1, there is a  triangle free planar graph G of maximum degree 4 on 3k-1 vertices for which \chi_c(G) = 3- 1/k.

I conjecture that this is the maximum value one can get.

Conjecture: If G is a triangle free planar graph of maximum degree 4  with |V(G)| < 3k, then chi_c(G) <= 3- 1/k.

Observe that it follows from Theorem 1 that  there is an infinite triangle free planar graph G of maximum degree 4 with chi_c(G) = 3.

¡@

References

[HR1] C. C. Heckman and R. Thomas,  A new proof of the independence ratio of triangle free cubic graphs. Discrete Mathematics, to appear.

[HR2]  C. C. Heckman and R. Thomas,  Independent sets in triangle free cubic planar graphs. Manuscript 2002.