Circular colorings of edge‐weighted graphs

Abstract

Abstract The notion of (circular) colorings of edge‐weighted graphs is introduced. This notion generalizes the notion of (circular) colorings of graphs, the channel assignment problem, and several other optimization problems. For instance, its restriction to colorings of weighted complete graphs corresponds to the traveling salesman problem (metric case). It also gives rise to a new definition of the chromatic number of directed graphs. Several basic results about the circular chromatic number of edge‐weighted graphs are derived. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 107–116, 2003