Premium
Circular colorings of weighted graphs
Author(s) -
Deuber Walter A.,
Zhu Xuding
Publication year - 1996
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/(sici)1097-0118(199612)23:4<365::aid-jgt6>3.0.co;2-p
Subject(s) - combinatorics , mathematics , chromatic scale , vertex (graph theory) , lexicographical order , graph , discrete mathematics
Suppose that G is a finite simple graph and w is a weight function which assigns to each vertex of G a nonnegative real number. Let C be a circle of length t . A t ‐circular coloring of ( G, w ) is a mapping Δ of the vertices of G to arcs of C such that Δ( x )∩Δ( y ) = 0 if ( x, y ) ∈ E ( G ) and Δ( x ) has length w ( x ). The circular‐chromatic number of ( G, w ) is the least t for which there is a t ‐circular coloring of ( G, w ). This paper discusses basic properties of circular chromatic number of a weighted graph and relations between this parameter and other graph parameters. We are particularly 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 that odd cycles and their complements are star‐superperfect. We then prove a theorem about the circular chromatic number of lexicographic product of graphs which provides a tool of constructing new star‐superperfect graphs from old ones. © 1996 John Wiley & Sons, Inc.