CIRCULAR COLORINGS OF WEIGHTED GRAPHS

Suppose that G is a finite simple graph and w is a weight function whi ch assigns to each vertex of G a nonnegative real number. Let C be a c ircle of length t. A t-circular coloring of (G, w) is a mapping a of t he vertices of G to arcs of C such that Delta(x) boolean AND Delta(y) = empty set if (x, y) is an element of E(G) and Delta(x) has length w( x). The circular-chromatic number of (G, w) is the least t for which t here is a t-circular coloring of (G, w). This paper discusses basic pr operties of circular chromatic number of a weighted graph and relation s between this parameter and other graph parameters. We are particular ly interested in graphs G for which the circular-chromatic number of ( G, w) is equal to the fractional clique weight of (G, w) for arbitrary weight function w, We call such graphs star-superperfect. We prove th at odd cycles and their complements are star-superperfect. We then pro ve a theorem about the circular chromatic number of lexicographic prod uct of graphs which provides a tool of constructing new star-superperf ect graphs from old ones. (C) 1996 John Wiley & Sons, Inc.