✦ LIBER ✦

Circular colorings of weighted graphs

✍ Scribed by Deuber, Walter A.; Zhu, Xuding

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 776 KB
Volume: 23
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199612)23:4<365::aid-jgt6>3.0.co;2-p

No coin nor oath required. For personal study only.

✦ Synopsis

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 A of the vertices of G to arcs of C such that A(%) n A(y) = 0 if (x, y) E E ( G ) and A(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.

📜 SIMILAR VOLUMES

Circular colorings of edge-weighted grap

Circular colorings of edge-weighted graphs

✍ Bojan Mohar 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB

## 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

Acrylic improper colorings of graphs

✍ Boiron, P.; Sopena, E.; Vignal, L. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 153 KB 👁 2 views

In this article, we introduce the new notion of acyclic improper colorings of graphs. An improper coloring of a graph is a vertex-coloring in which adjacent vertices are allowed to have the same color, but each color class V i satisfies some condition depending on i. Such a coloring is acyclic if th

Oriented list colorings of graphs

✍ Zs. Tuza; M. Voigt 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB 👁 1 views

A 2-assignment on a graph G (V,E) is a collection of pairs Lv of allowed colors speci®ed for all vertices v PV. The graph G (with at least one edge) is said to have oriented choice number 2 if it admits an orientation which satis®es the following property: For every 2-assignment there exists a choic

Acyclic edge colorings of graphs

✍ Noga Alon; Benny Sudakov; Ayal Zaks 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

## Abstract A proper coloring of the edges of a graph __G__ is called __acyclic__ if there is no 2‐colored cycle in __G__. The __acyclic edge chromatic number__ of __G__, denoted by __a′__(__G__), is the least number of colors in an acyclic edge coloring of __G__. For certain graphs __G__, __a′__(_

Face colorings of embedded graphs

✍ Dan Archdeacon 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 498 KB

We characterize those graphs which have at least one embedding into some surface such that the faces can be properly colored in four or fewer colors. Embeddings into both orientable and nonorientable surfaces are considered.

On Total Colorings of Graphs

✍ C. Mcdiarmid; B. Reed 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 299 KB

AND Bruce Reed Department of Combinatorics and Optimisation, University of Waterloo, Waterloo, Ontario, Canada