Curvature from Graph Colorings

Abstract

Given a finite simple graph G=(V,E) with chromatic number c and chromatic polynomial C(x). Every vertex graph coloring f of G defines an index i_f(x) satisfying the Poincare-Hopf theorem sum_x i_f(x)=chi(G). As a variant to the index expectation result we prove that E[i_f(x)] is equal to curvature K(x) satisfying Gauss-Bonnet sum_x K(x) = χ(G), where the expectation is the average over the finite probability space containing the C(c) possible colorings with c colors, for which each coloring has the same probability.

14 pages, 6 figures

References in corpus (2)

• On index expectation and curvature for networks
• An index formula for simple graphs

Cited by in corpus (10)

• Coloring graphs using topology
• The strong ring of simplicial complexes
• Dehn-Sommerville from Gauss-Bonnet
• Characteristic Length and Clustering
• The Kuenneth formula for graphs
• Integral geometric Hopf conjectures
• On Atiyah-Singer and Atiyah-Bott for finite abstract simplicial complexes
• Constant index expectation curvature for graphs or Riemannian manifolds
• Graph complements of circular graphs
• The Curvature of Graph Products