Premium
Circular colorings of edge‐weighted graphs
Author(s) -
Mohar Bojan
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10106
Subject(s) - combinatorics , mathematics , chromatic scale , chordal graph , indifference graph , edge coloring , discrete mathematics , graph , line graph , graph power
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