Ollivier's Ricci curvature and the coloring of graphs

摘要

We obtain lower bounds on the clique number and chromatic number for finite simple graphs using Ollivier's Ricci curvature. Also we study the relations between girth and curvature. From these, we obtain curvature conditions for 3-colorability of a planar graph.