Coloring graphs using topology

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.

81 pages, 48 figures

References in corpus (16)

• A graph theoretical Gauss-Bonnet-Chern Theorem
• A graph theoretical Poincare-Hopf Theorem
• On index expectation and curvature for networks
• The McKean-Singer Formula in Graph Theory
• The Dirac operator of a graph
• An index formula for simple graphs
• The Lusternik-Schnirelmann theorem for graphs
• A notion of graph homeomorphism
• Curvature from Graph Colorings
• An integrable evolution equation in geometry
• The Euler characteristic of an even-dimensional graph
• Classical mathematical structures within topological graph theory
• Isospectral deformations of the Dirac operator
• The theorems of Green-Stokes,Gauss-Bonnet and Poincare-Hopf in Graph Theory
• Characteristic Length and Clustering
• If Archimedes would have known functions

Cited by in corpus (15)

• Gauss-Bonnet for multi-linear valuations
• Graphs with Eulerian unit spheres
• The amazing world of simplicial complexes
• The Jordan-Brouwer theorem for graphs
• Sphere geometry and invariants
• A Sard theorem for graph theory
• The graph spectrum of barycentric refinements
• The Kuenneth formula for graphs
• A Reeb sphere theorem in graph theory
• A simple sphere theorem for graphs
• Combinatorial manifolds are Hamiltonian
• Graph complements of circular graphs
• Eulerian edge refinements, geodesics, billiards and sphere coloring
• Complexes, Graphs, Homotopy, Products and Shannon Capacity
• Coloring Discrete Manifolds