Current status of questions concerning circular chromatic number asked in  survey.

Question 8.1:  Characterize those planar graphs G with chi_c(G) = 4 and those planar graphs G with chi_c(G) = 3. 

Open.

Question 8.2: Prove that chi_c(G) < 5 for every planar graph G without using the Four Color Theorem.

Open.

Question 8.3: Prove that if G is a 2-edge connected cubic planar graph, and H=L(G) is the line graph of G, then chi_c(H) < 4, without using the Four Color Theorem.

It is proved (see here) by Afshani,  Mahsa Ghandehari, Mahya Ghandehari, Hatami, Tusserkani and Xuding Zhu (preprint) that every 2-edge connected cubic graph G has chi_c(L(G)) <= 11/3. This bound is sharp as Petersen graph has circular edge chromatic number 11/3.

Question 8.4: Are there any 2-edge connected cubic graph G whose line graph has circular chromatic number 4 ?

Answered as above. 

Question 8.5: For any integer n >= 1, what are the possible values of the circular chromatic numbers of graphs embeddable on the surface (orientable) of genus n ?

Open.

Question 8.6:  Does there exists an epsilon > 0 and an integer n such that for every rational 4 <= r <= 4 + epsilon, there exists a graph G embeddable on the surface of (orientable) genus n, and chi_c(G) = r ?

Open.

Question 8.7: What are the possible values of the circular flow numbers of graphs ? Is it true that for any rational 2 <= r <= 5, there is a graph G with circular flow number r ?

It is proved in [PZ] that for any rational 2 <= r <= 5, there is a graph G with circular flow number r. So if Tutte's 5-flow conjecture is true, then this question is solved.

Question 8.8:  For which rational number r, there is a graph G whose line graph L(G) has circular chromatic number r ? In particular, is it true that for any rational r >=3, there exists a graph G with chi_c(L(G)) = r ?

It is proved in [AGGHTZ04] that (11/3, 4) is a gap for circular chromatic indexes, i.e., there is no graph G whose circular chromatic index lies in the interval (11/3, 4).

It is proved by Daniel Kral, Edita Macajova, Jan Mazak and Jean-Sebastien Sereni [KMMS09] that subcubic graphs of girth at least 6 has circular chromatic index at most 7/2. Currently no graphs are known to have circular chromatic index in the interval (7/2, 11/3).

On the other hand, it is proved by Robert Lukotka and Jan Mazak [LM09] that for any rational number r \in (3, 10/3), there is a graph cubic graph G with circular chromatic index r. 

The question of determining all the possible values of the circular chromatic indices of subcubic graphs remains open. Some interesting sub-questions are:

1: are there graphs with circular chromatic index in the interval (7/2,11/3)?

2: what is the largest number s such that every rational r \in (3, s) is the circular chromatic index of some graph?

3: is there a connected graph other than the Petersen graph with circular chromatic index 11/3?

Question 8. 9:  Is it true that for any n >=5, for any rational 2 <= r <= n-1, there is a K_n-minor free graph with circular chromatic number r ?

This question is answered in the affirmative in  [LPZ].

Question 8.10:  Are there other gaps among the circular chromatic number of series-parallel graphs ? What rationals are the circular chromatic numbers of series-parallel graphs ?

This question is answered in [PZdense]: there are no other gaps. [2, 8/3] \cup {3} is the set of rationals which are the circular chromatic numbers of series-parallel graphs.

Question 8.11:  Suppose H is a fixed finite graph, and epsilon > 0. Does there exist an integer f(H, epsilon) such that the following is true: if G is a graph of girth at least f(H, epsilon) and G' is a H-minor free graph admitting a homomorphism to G then chi_c(G') <= 2 + epsilon ?

Open.

Question 8.12: Is it true that for any epsilon > 0 and for any integer k, there is an integer f(epsilon, k) such that for any graph G of treewidth at most k and of odd girth at least f(epsilon, k) has circular chromatic number at most 2 + epsilon ?

(Maybe solved) 

Question 8.13: Is it true that chi_c(G x H) = min{ chi_c(G), chi_c(H)} ?

Open. However, it is proved by Claude Tardif  that if min{ chi_c(G), chi_c(H)} < 4, then chi_c(G x H) = min{ chi_c(G), chi_c(H)}.

Question 8.14: What is the least integer g(n) such that any n-critical graph G with girth at least g(n) has chi_c(G) < chi(G) ? 

Open.

Question 8.15: For any integer n >=4, does there exist an integer m such that there are arbitrarily large n-critical graph G which has maximum degree at most m and for which chi_c(G) = chi(G) ? If there exists such an integer, let Delta(n) be the least one of such integers. What is Delta(n) for n >= 4 ?

It is proved by Lam, Lin, Gu and Song [JCTB 89(2)(2003), 195-205] that if n is even, then Delta(n) <= 2n-4. For odd n, a similar result is in preparation.

Question 8. 16: Is it true that every graph G has a vertex v such that chi_c(G-v) >= chi_c(G)-1 ?

See here.

Question 8.17:  Let r, r' be any rational numbers such that 2 < r < r' and {r} >= {r'} -1. Does there exist a graph G and a vertex v of G such that chi_c(G)  = r' and chi_c(G-v) = r ?

Open.

Question 8.18: For which graph G, chi_c(G-v) = chi_c(G)-1 for each vertex v of G ?

Open.  

Question 8.19: Are there two rationals 2 < r < r' such that any graph of circular chromatic number r' contains a subgraph of circular chromatic number r ?

See here.

Question 8.20: For which graph G, we have chi_c(H) = chi(H) for any induced subgraph H of G ?

Answer: G is a perfect graph. This answer follows from the Strong Perfect Graph Theorem proved by Chudnovsky, Robertson, Seymour and Thomas.

Question 8.21:  Is it true that chi_c(H) =chi(H)  for every induced subgraph of G implies that chi_c(H) =chi(H)  for every induced subgraph of the complement of G ?

Answer follows from  the Strong Perfect Graph Theorem.

Question 8.22:  For which graphs G, we have chi_c(G) = chi_f(G) ? And for which graph G we have chi_c(H) = chi_f(H) for every induced subgraph H of G ? 

Open.

Question 8.23: What is the complexity of determining whether or not chi_c(G) = chi(G) if the chromatic number chi(G) is known ?

Answered by Hatami and Tusserkani (preprint): NP-hard. 

Question 8.24: Is it true that chi(G) - chi_c(G) <= chi(M^2(G)) - chi_c(M^2(G)) ? 

Open.

Question 8.25: What determines whether chi_c(M(G)) = chi(M(G)) ? In particular, for coprime integers k, d with 2d < k, is it true that chi_c(M(G^k_d)) = chi(M(G^k_d)) ? 

It is proved by Huang, Lingling and Chang, Gerard J. [JGT, 32(1999), 63-71]  that chi_c(M(G^k_d)) = chi(M(G^k_d)). The other part of the question remains open.

Question 8.26: Suppose D={a, b, c}, what is the circular chromatic number of G(Z,D) ?

Open.

Question 8.27: Is it true that for any Kneser graph KG(m, n), chi_c(KG(m, n)) = chi(KG(m, n)) ?

It is partially answered by Hajiabolhassan and Zhu , who proved that if m >= 2n^2(n-1), then the equality holds. 

Recently, it is proved by  Gabor Simonyi and Gabor Tardos [ST], and independently by Frederic Meunier,  that if chi(KG(m,n)) is even, then chi_c(KG(m, n)) = chi(KG(m, n)).  

Indeed, Gabor Simonyi and Gabor Tardos [ST] and Frederic Meunier proved that if chi(KG(m,n)) is even, then the Schrijver graph SG(m, n)  has its circular chromatic number equals chi(KG(m,n)). The Schrijver graph SG(m, n)  is the subgraph of KG(m, n) induced by "stable-n-subsets", i.e., each vertex of SG(m, n) is an n-subset A of {0, 1, ..., m-1} such that if i \in A, then i+1 \not\in A;  if m-1 \in A then 0 \not\in A.  Gabor Simonyi and Gabor Tardos also proved that for any odd number t, then for any epsilon > 0, there is an integer n*, such that for any n > n*, for m=2n-2+t,   t-1 < \chi_c(SG(m, n)) < t-1 + \epsilon. It was conjectured by Lih-Liu [JGT 41(2002), 62-68] that 

for each fixed n, if m is large enough , then the Schrijver graph SG(m,n) has chi_c = chi.  

This conjecture was confirmed in [Hajiabolhassan and Zhu ]. However, it remains open as for which m, chi_c(SG(m, n)) = chi(SG(m, n)).  　

Question 8.28: Is it possible to construct all graphs G with chi_c(G) >= k/d from copies of G^k_d by following some simple rules (such as those in Hajos theorem) ?

Such constructions are given in [Zhu] for k/d >=3 and in [Zhu2] for 2 < k/d < 3.