zbMATH — the first resource for mathematics

Circular colorings of edge-weighted graphs. (English) Zbl 1014.05026
Summary: 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.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Deuber, J Graph Theory 23 pp 365– (1996)
[2] Ghouila-Houri, C. R. Acad Sciences 250 pp 3931– (1960)
[3] Goddyn, J Graph Theory 28 pp 155– (1998)
[4] Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, In: ?Combinatorial Analysis: Proc. of the Tenth Symp. in Appl. Math. of the AMS?, and (Editors), Amer Math Soc, 1960, pp. 113-128.
[5] Bounds for the span in channel assignment problems, talk at the 18th British Combinatorial Conference, July 2001.
[6] Discrete mathematics and radio channel assignment, In: ?Recent advances in theoretical and applied discrete mathematics?, and (Editors), to appear.
[7] Minty, Amer Math Monthly 69 pp 623– (1962)
[8] Haj?s theorem for colorings of edge-weighted graphs, submitted. · Zbl 1070.05043
[9] Zhu, Discrete Math 229 pp 371– (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.