¡@

Subgraphs induced by a circular coloring

Conjecture    Suppose G is a graph with chi_c(G) = p/q. Then for any (p, q)-coloring f  of G, there is a subgraph H of G such that the following holds.

For any vertex x* of H,  for any (p, q)-coloring g  of H, if  g(x) = f(x)  for all  x \neq x*, then  g(x*) = f(x*).

In other words, in the (p, q)-coloring f  of H,  the colors of  H\x* uniquely determines the color of x*.

The conjecture is true for p/q < 4. It is known [Zhu01]  that if chi_c(G) = p/q, then for any (p, q)-coloring f of G, there is a cycle  C=( x_0, x_1, ..., x_{n-1} ) such that  for all i, f(x_{i+1}) - f(x_i)  = q mod(p). It is not difficult to see that  in such a (p, q)-coloring of C,  for any i, the colors of C\x_i uniquely determines the color of x_i.

Note added 25.02.2008: This conjecture is false, as shown by David Cariolaro. Let G be obtained from K_4 by subdividing one edge with a vertex. The line graph L(G) of G has circular chromatic number 4.  Colour the edge edges incident to the degree 2 vertex by 0,1, the edge not incident to any of these two edges by colour 1, and the  other 4 edges as 3,2,3,2. The colours of a triangle 3,2,1 can be individually changed to 0, so none of them should be in H. After deleting this triangle, it is easy to see that no other edges should be in H. Hence H does not exists.

¡@

                                                                                                                      

¡@