Chi_c of line graphs
¡@
Question 1 What are the possible values of the circular chromatic number of line graphs ?
Question 2 Does there exist a 2-edge connected cubic graph G whose line graph L(G) has circular chromatic number chi_c( L(G) ) > 11/3 ?
The line graph of the Petersen graph has circular chromatic number 11/3. A negative answer to Question 2 is implies by the Petersen coloring conjecture of Jaeger.
The Petersen coloring conjecture [Jaeger] If G is a 2-edge connected cubic graph, then L(G) admits a homomorphism to L(P), where P is the Petersen graph.
Question 2 has been answered in the negative in [AGGHTZ]. It is proved in [AGGHTZ] that every 2-edge connected graph G of maximum degree at most 3 has chi_c(L(G)) =< 11/3, with two exceptions H1 and H2. Where H2 is obtained from the complete graph K4 by subdividing one edge, and H1 is obtained as follows: Let K be the graph with two vertices and three parallel edges. Then H1 is obtained from K by subdividing one edge,
To replace Question 2, we ask the following questions:
Question 3 Is it true that for each integer k > 1, there is an epsilon > 0 such that for any line graph L(G), either chi_c(L(G)) >= k or chi_c(L(G)) =< k - epsilon ?
For k=2, 3, 4, the epsilon exist, and the maximum such epsilon for k=2, 3, 4 are 1, 1/2, 1/3, respectively. So if the answer to Question 3 is positive, then the next question is whether epsilon can be chosen as 1/(k-1).
Question 4 If the answer to Question 3 is positive, is it true that the maximum value of such an epsilon is 1/(k-1) ?
For k=3, C_5 is a graph with chi_c(L(C_5)) = 3- 1/2. For k =4, the Petersen graph G is a graph with chi_c(L(G)) = 4- 1/3. As part of Question 4, we
Question 5 For k >=5, is there a graph G with chi_c(L(G)) = k- 1/(k-1) ?