Czechoslovak Mathematical Journal, first online, pp. 1-31


Fundamental groupoids of digraphs and graphs

Alexander Grigor'yan, Rolando Jimenez, Yuri Muranov

Received December 18, 2015.   First published January 15, 2018.

Abstract:  We introduce the notion of fundamental groupoid of a digraph and prove its basic properties. In particular, we obtain a product theorem and an analogue of the Van Kampen theorem. Considering the category of (undirected) graphs as the full subcategory of digraphs, we transfer the results to the category of graphs. As a corollary we obtain the corresponding results for the fundamental groups of digraphs and graphs. We give an application to graph coloring.
Keywords:  digraph; fundamental group; fundamental groupoid; product of graphs
Classification MSC:  05C25, 05C38, 05C76, 20L05, 57M15
DOI:  10.21136/CMJ.2018.0683-15

PDF available at:  Springer   Institute of Mathematics CAS

References:
[1] R. H. Atkin: An algebra for patterns on a complex I. Int. J. Man-Mach. Stud. 6 (1974), 285-307. DOI 10.1016/S0020-7373(74)80024-6 | MR 0424293
[2] R. H. Atkin: An algebra for patterns on a complex II. Int. J. Man-Mach. Stud. 8 (1976), 483-498. DOI 10.1016/S0020-7373(78)80015-7 | MR 0574079
[3] E. Babson, H. Barcelo, M. de Longueville, R. Laubenbacher: Homotopy theory of graphs. J. Algebr. Comb. 24 (2006), 31-44. DOI 10.1007/s10801-006-9100-0 | MR 2245779 | Zbl 1108.05030
[4] H. Barcelo, X. Kramer, R. Laubenbacher, C. Weaver: Foundations of a connectivity theory for simplicial complexes. Adv. Appl. Math. 26 (2001), 97-128. DOI 10.1006/aama.2000.0710 | MR 1808443 | Zbl 0984.57014
[5] R. Brown: Topology and Groupoids. BookSurge, Charleston (2006). MR 2273730 | Zbl 1093.55001
[6] A. Dimakis, F. Müller-Hoissen: Differential calculus and gauge theory on finite sets. J. Phys. A, Math. Gen. 27 (1994), 3159-3178. DOI 10.1088/0305-4470/27/9/028 | MR 1282159 | Zbl 0843.58004
[7] A. Dimakis, F. Müller-Hoissen: Discrete differential calculus: Graphs, topologies, and gauge theory. J. Math. Phys. 35 (1994), 6703-6735. DOI 10.1063/1.530638 | MR 1303075 | Zbl 0822.58004
[8] A. Grigor'yan, Y. Lin, Y. Muranov, S.-T. Yau: Homotopy theory for digraphs. Pure Appl. Math. Q. 10 (2014), 619-674. DOI 10.4310/PAMQ.2014.v10.n4.a2 | MR 3324763 | Zbl 1312.05063
[9] A. Grigor'yan, Y. Lin, Y. Muranov, S.-T. Yau: Cohomology of digraphs and (undirected) graphs. Asian J. Math. 19 (2015), 887-931. DOI 10.4310/AJM.2015.v19.n5.a5 | MR 3431683 | Zbl 1329.05132
[10] A. Grigor'yan, Y. V. Muranov, S.-T. Yau: Graphs associated with simplicial complexes. Homology Homotopy Appl. 16 (2014), 295-311. DOI 10.4310/HHA.2014.v16.n1.a16 | MR 3211747 | Zbl 1297.05269
[11] A. Hatcher: Algebraic Topology. Cambridge University Press, Cambridge (2002). MR 1867354 | Zbl 1044.55001
[12] P. Hell, J. Nešetřil: Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and Its Applications 28, Oxford University Press, Oxford (2004). DOI 10.1093/acprof:oso/9780198528173.001.0001 | MR 2089014 | Zbl 1062.05139
[13] E. H. Spanier: Algebraic Topology. Springer, Berlin (1995). DOI 10.1007/978-1-4684-9322-1 | MR 1325242 | Zbl 0810.55001

Affiliations:   Alexander Grigor'yan, Mathematics Department, University of Bielefeld, Universitätsstrasse 25, P. O. Box 100131, D-33501, Bielefeld, Germany, e-mail: grigor@math.uni-bielefeld.de; Rolando Jimenez, Instituto de Matematicas, UNAM Unidad Oaxaca, Leon 2, Centro, 68000 Oaxaca, Mexico, e-mail: rolando@matcuer.unam.mx; Yuri Muranov, Faculty of Mathematics and Computer Science, University of Warmia and Mazury, Sloneczna 54 Street, 10-710 Olsztyn, Poland, e-mail: muranov@matman.uwm.edu.pl


 
PDF available at: