A Dynamic View of Circular Colorings

Simple item page
dc.creatorYeh, Hong-Gwa
dc.date2006-04-10
dc.date.accessioned2026-07-07T07:10:43Z
dc.date.available2026-07-07T07:10:43Z
dc.descriptionThe main contributions of this paper are three-fold. First, we use a dynamic approach based on Reiter's pioneering work on Karp-Miller computation graphs to give a new and short proof of Mohar's Minty-type Theorem. Second, we bridge circular colorings and discrete event dynamic systems to show that the Barbosa and Gafni's results on circular chromatic number can be generalized to edge-weighted symmetric directed graphs. Third, we use the above-mentioned dynamic view of circular colorings to construct new improved lower bounds on the circular chromatic number of a graph. We show as an example that the circular chromatic number of the line graph of the Petersen graph can be determined very easily by using these bounds.
dc.description23 pages
dc.identifierhttps://arxiv.org/abs/math/0604226
dc.identifierhttp://arxiv.org/abs/math/0604226
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/111512
dc.subjectCombinatorics
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectDiscrete Mathematics
dc.subject05C15 (Primary) 68R05, 90B35, 68M14, 68M20(Secondary)
dc.titleA Dynamic View of Circular Colorings
dc.typetext

Files

Collections

arXiv