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.