Topological and Algebraic Lower Bounds on the Chromatic Number of Graphs

Abstract

In this paper we present a survey of various lower bounds on graph chromatic number. We present lower bounds derived both from elementary graph invariants, as well as invariants of topological spaces derived from the combinatorial structure of graphs. We discuss the graph U(5,3) as an example where some of these bounds differ.