{
  "id": "1412.6985",
  "version": "v1",
  "published": "2014-12-22T14:06:37.000Z",
  "updated": "2014-12-22T14:06:37.000Z",
  "title": "Coloring graphs using topology",
  "authors": [
    "Oliver Knill"
  ],
  "comment": "81 pages, 48 figures",
  "categories": [
    "math.CO",
    "cs.CG",
    "cs.DM",
    "math.GT"
  ],
  "abstract": "Higher dimensional graphs can be used to colour two-dimensional geometric graphs. If G the boundary of a three dimensional graph H for example, we can refine the interior until it is colourable with 4 colours. The later goal is achieved if all interior edge degrees are even. Using a refinement process which cuts the interior along surfaces we can adapt the degrees along the boundary of that surface. More efficient is a self-cobordism of G with itself with a host graph discretizing the product of G with an interval. It follows from the fact that Euler curvature is zero everywhere for three dimensional geometric graphs, that the odd degree edge set O is a cycle and so a boundary if H is simply connected. A reduction to minimal colouring would imply the four colour theorem. The method is expected to give a reason \"why 4 colours suffice\" and suggests that every two dimensional geometric graph of arbitrary degree and orientation can be coloured by 5 colours: since the projective plane can not be a boundary of a 3-dimensional graph and because for higher genus surfaces, the interior H is not simply connected, we need in general to embed a surface into a 4-dimensional simply connected graph in order to colour it. This explains the appearance of the chromatic number 5 for higher degree or non-orientable situations, a number we believe to be the upper limit. For every surface type, we construct examples with chromatic number 3,4 or 5, where the construction of surfaces with chromatic number 5 is based on a method of Fisk. We have implemented and illustrated all the topological aspects described in this paper on a computer. So far we still need human guidance or simulated annealing to do the refinements in the higher dimensional host graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-12-22T14:06:37.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C10",
      "57M15"
    ],
    "keywords": [
      "coloring graphs",
      "chromatic number",
      "dimensional graph",
      "higher dimensional host graph",
      "colour two-dimensional geometric graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 81,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1412.6985K"
    }
  }
}