A note on circular colorings of edge-weighted digraphs

Wu-Hsiung Lin, Hong Gwa Yeh*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

An edge-weighted digraph (G, ℓ) is a strict digraph G together with a function ℓ assigning a real weight ℓuv to each arc uv. (G, ℓ) is symmetric if uv is an arc implies that so is vu. A circular r-coloring of (G, ℓ) is a function φ assigning each vertex of G a point on a circle of perimeter r such that, for each arc uv of G, the length of the arc from φ(u) to φ(v) in the clockwise direction is at least ℓuv. The circular chromatic number χc(G, ℓ) of (G, ℓ) is the infimum of real numbers r such that (G, ℓ) has a circular r-coloring. Suppose that (G, ℓ) is an edge-weighted symmetric digraph with positive weights on the arcs. Let T be a {0, 1}-function on the arcs of G with the property that T(uv) + T(vu) = 1 for each arc uv in G. In this note we show that if, for each dicycle C of G satisfying, then (G, ℓ) has a circular r-coloring.

Original languageEnglish
Pages (from-to)2159-2167
Number of pages9
JournalTaiwanese Journal of Mathematics
Volume15
Issue number5
DOIs
StatePublished - 1 Jan 2011

Keywords

  • Circular chromatic number
  • Digraph

Fingerprint Dive into the research topics of 'A note on circular colorings of edge-weighted digraphs'. Together they form a unique fingerprint.

Cite this