A NOTE ON CIRCULAR COLORINGS OF EDGE-WEIGHTED DIGRAPHS

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/51177

Title:	A NOTE ON CIRCULAR COLORINGS OF EDGE-WEIGHTED DIGRAPHS
Authors:	Lin,WH;Yeh,HG
Contributors:	數學系
Keywords:	CHROMATIC NUMBER;GRAPHS
Date:	2011
Issue Date:	2012-03-27 18:24:09 (UTC+8)
Publisher:	國立中央大學
Abstract:	An edge-weighted digraph ((G) over right arrow, l) is a strict digraph (G) over right arrow together with a function l assigning a real weight l(uv) to each arc uv. ((G) over right arrow, l) is symmetric if uv is an arc implies that so is vu. A circular r-coloring of ((G) over right arrow, l) is a function phi assigning each vertex of (G) over right arrow a point on a circle of perimeter r such that, for each arc uv of (G) over right arrow, the length of the arc from phi(u) to phi(v) in the clockwise direction is at least l(uv). The circular chromatic number chi(c)((G) over right arrow, l) of ((G) over right arrow, l) is the infimum of real numbers r such that ((G) over right arrow, l) has a circular r-coloring. Suppose that ((G) over right arrow, l) is an edge-weighted symmetric digraph with positive weights on the arcs. Let T be a {0,1}-function on the arcs of (G) over right arrow with the property that T(uv) + T(vu) = 1 for each arc uv in (G) over right arrow. In this note we show that if Sigma(uv is an element of E((C) over right arrow)) l(uv)/Sigma(uv is an element of E((C) over right arrow)) T(uv) <= r for each dicycle (C) over right arrow of (G) over right arrow satisfying 0 < (Sigma(uv is an element of E(<(C)over right arrow>)) l(uv)) mod r < max{l(xy) + l(xy) : xy is an element of E(<(G)over right arrow>)}, then ((G) over right arrow, l) has a circular r-coloring. Our result generalizes the work of Zhu, J. Comb. Theory, Ser B, 86 (2002), 109-113, and also strengthens the work of Mohar, J. Graph Theory, 43 (2003), 107-116.
Relation:	TAIWANESE JOURNAL OF MATHEMATICS
Appears in Collections:	[Department of Mathematics] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	754	View/Open

社群 sharing

Loading...