Fundamental groupoids for graphs

Document Type : Research Paper


1 Montana State University-Billings

2 Fort Lewis College


In recent years several notions of discrete homotopy for graphs have been introduced, including a notion of ×-homotopy due to Dochtermann. In this paper, we define a ×-homotopy fundamental groupoid for graphs, and prove that it is a functorial ×-homotopy invariant for finite graphs. We also introduce tools to compute this fundamental groupoid, including a van Kampen theorem. We conclude with a comparison with previous definitions along these lines, including those built on polyhedral complexes of graph morphisms.


[1] Babson, E., Barcelo, H., Longueville, M., and Laubenbacher, R., Homotopy theory of graphs, Algebraic Combin. 24 (2006), 31-44.
[2] Babson, E. and Kozlov, D., Complexes of graph homomorphisms, Isreal J. Math. 24 (2006), 285-312.
[3] Barcelo, H., Kramer, X., Laubenbacher, R. and Weaver, C., Foundations of a connectivity theory for simplicial complexes, Adv. Appl. Math. 26 (2001), 31-44.
[4] Bonato, A. and Nowakowski, R., “The Game of Cops and Robbers”, American Mathematical Society, 2010.
[5] Bondy, J. and Murty, U.S.R., “Graph Theory”, Springer, 2008.
[6] Brightwell, G. and Winkler, P., Gibbs measures and dismantlable graphs, J. Combin. Theory Ser. B. 78 (2000), 141-166.
[7] Brown, R., Groupoids and Van Kampen’s Theorem, Proc. Lond. Math. Soc. 17(3) (1967), 385-401.
[8] Bubenik, P. and Milićević, N., Homotopy, homology and persistent homology using Cech’s closure spaces,
[9] Chih, T. and Scull, L., A homotopy category for graphs, Algebraic Combin. 53 (2021), 1231-1251.
[10] Chih, T. and Scull, L., Homotopy covers of graphs,
[11] Dochtermann, A., Hom complexes and homotopy theory in the category of graphs, European J. Combin. 30 (2009), 490-509.
[12] Dochtermann, A., Homotopy groups of Hom complexes of graphs, J. Combin. Theory Ser. A. 116 (2009), 180-194.
[13] Dochtermann, A. and Singh, A., Homomorphism complexes, reconfiguration, and homotopy for directed graphs,
[14] Fieux, E. and Lacaze, J., Foldings in graphs and relations with simplicial complexes and posets, Discrete Math. 312 (2012), 2639-2651.
[15] Grigor’yan, A. and Lin, Y., Muranov, Y., and Yau, S.T., Homotopy theory for digraphs, Pure Appl. Math. Q. 10(4) (2014), 619-674.
[16] Hardeman, R., The lifting properties of A-homotopy theory,
[17] Hatcher, A., “Algebraic Topology”, Cambridge University Press, 2001.
[18] Hell, P. and Neˇsetˇril, J., “Graphs and homomorphisms”, Oxford University Press,2004.
[19] Kozlov, D., Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes,
[20] Kozlov, D., Collapsing along monotone poset maps, Int. J. Math. Math. Sci. (2006), Article ID 079858, 8 pages.
[21] Kozlov, D., Simple homotopy types of Hom-complexes, neighborhood complexes, Lovasz complexes, and atom crosscut complexes, Topology Appl. 14 (2006), 2445-2454.
[22] Kozlov, D., A simple proof for folds on both sides in complexes of graph homomorphisms, Proc. Amer. Math. Soc. 134 (2006), 1265-1270.
[23] Kwak, J.J. and Nedela, R. “Graphs and Their Coverings”, 2005,
[24] Lutz, B., Higher discrete homotopy groups of graphs,
[25] Matsushita, T., Box complexes and Homotopy theory of graphs, Homology Homotopy Appl. 19 (2017), 175-197.
[26] Plessas, D., The Categories of Graphs, University of Montana Graduate Student Theses, Dissertations, & Professional Papers (2012).
[27] Riehl, E., “Category Theory in Context”, Dover Publications, 2017.