Pure and Applied Mathematics Quarterly

Volume 10 (2014)

Number 4

Homotopy Theory for Digraphs

Pages: 619 – 674

DOI: http://dx.doi.org/10.4310/PAMQ.2014.v10.n4.a2

Authors

Alexander Grigor’yan (Department of Mathematics, University of Bielefeld, Germany)

Yong Lin (Department of Mathematics, Renmin University of China, Haidian, Beijing, China)

Yuri Muranov (Department of Mathematics, University of Warmia and Mazury, Olsztyn, Poland)

Shing-Tung Yau (Department of Mathematics, Harvard University, Cambridge, Massachusetts, U.S.A.)

Abstract

We introduce a homotopy theory of digraphs (directed graphs) and prove its basic properties, including the relations to the homology theory of digraphs constructed by the authors in previous papers. In particular, we prove the homotopy invariance of homologies of digraphs and the relation between the fundamental group of the digraph and its first homology group.

The category of (undirected) graphs can be identified by a natural way with a full subcategory of digraphs. Thus we obtain also consistent homology and homotopy theories for graphs. Note that the homotopy theory for graphs coincides with the one constructed in [1] and [2].

Keywords

homotopy of digraphs, homology of digraphs, fundamental group of digraphs, homotopy groups of digraphs, homology of graphs, homotopy of graphs, graph coloring, algebraic topology for digraphs

Full Text (PDF format)