Stelian Mihalas

Graph Dimension and Related Colorings: the Cellular Structures of Graphs, Their Geometric Representations and the Chromatic Information They Reveal Stelian Mihalas

This paper provides a geometric alternative to the concept of graph dimension, concept defined in rather obscure analytical terms by Colin de Verdiere. The equivalence of these two definitions is shown in low dimension. When viewed as the 1-skeleton of a simplicial complex, the cellular structure of the graph provides significant information about its chromatic polynomial. This information is detailed in the particular case of near-triangulations of the 2-sphere. The concept of coloring functor from the category of simplicial complexes and regular simplicial maps to the category of abelian groups is definded and studied in low dimension. The final result of the thesis establishes a necessary and sufficient condition for a subcomplex of a 2-sphere triangulation to be the singular subcomplex of a 4-coloring of the associated graph.