{
  "id": "math/0604226",
  "version": "v1",
  "published": "2006-04-10T16:02:53.000Z",
  "updated": "2006-04-10T16:02:53.000Z",
  "title": "A Dynamic View of Circular Colorings",
  "authors": [
    "Hong-Gwa Yeh"
  ],
  "comment": "23 pages",
  "categories": [
    "math.CO",
    "cs.DC",
    "cs.DM"
  ],
  "abstract": "The 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-04-10T16:02:53.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "68R05",
      "90B35",
      "68M14",
      "68M20"
    ],
    "keywords": [
      "circular chromatic number",
      "discrete event dynamic systems",
      "mohars minty-type theorem",
      "bridge circular colorings",
      "karp-miller computation graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math......4226Y"
    }
  }
}