Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
Dmitry N. Kozlov · IAS/Park City mathematics series · 2007
Introduction.1.1.The chromatic number of a graph.1.1.1.The definition and applications.Unless stated otherwise, all graphs are undirected, loops are allowed, whereas multiple edges are not.We shall occasionally stress these conventions, to avoid the possibility of misunderstanding.For a graph G, V (G) denotes the set of its vertices, and E(G) denotes the set of its edges.If convenient, we think ofwhere Z 2 acts on V (G)×V (G) by switching the coordinates: (x, y) → (y, x).Under this convention, a looped vertex x is encoded by the diagonal element (x, x), while the edge from x to y (for x = y) is encoded by the pair (x, y), (y, x) ∈ V (G) × V (G).For example, the edge set of the graph with 2 vertices connected by an edge, were the first vertex is looped, and the second one is not, is encoded by the setClearly, a vertex coloring exists if and only if G has no loops.Definition 1.1.2.The chromatic number of G, χ(G), is the minimal cardinality of a finite set S, such that there exists a vertex-coloring c : V (G) → S.