Construction of Cores
by
Zhongyuan Che
Wesleyan University
Coauthors: Karen L. Collins (Wesleyan University)

A graph homomorphism from G to H is a mapping f:V(G) --> V(H) such that g ~ g' in G implies f(g) ~ f(g') in H. A graph G is a core if there is no homomorphism from G to any of its proper induced subgraphs. An induced subgraph G^* of G is called the core of G if G --> G^* and G^* is a core. Since there exist homomorphisms between G and G^* in both directions, chi(G)=chi(G^*). A graph G is chi-critical if the chromatic number of every proper subgraph are strictly less than chi(G). It follows that any chi-critical graph is a core. Let k and d be positive integers such that k >= 2d. A (k, d)-coloring of a graph G=(V, E) is a mapping c:V --> [k] such that if u ~ v, then d <= |c(u)-c(v)| <= k-d. A (k, 1)-coloring of G is simply a proper k-coloring of G; therefore the chromatic number chi(G) is the smallest k for which G admits a (k, 1)-coloring. The circular chromatic number chi_c(G) (or star chromatic number chi^*(G)) of a graph G is defined by chi_c(G)=inf{[ k/d]:G has a (k, d)-coloring}. It is well known that a chi_c-critical graph is also a core. It is natural to ask if cores are always chi_c-critical.

Let G ^[¯] H be the Cartesian product and G[H] be wreath product of graphs G and H. In this note we prove that: C_2k+1^[¯] P and C_2k+1[P] are cores, but they are not chi_c-critical for k >= 1.

Date received: April 19, 2001