Multipath matroids, digraph colourings, and the Tutte polynomial
We introduce the MP-digraphs, a class of directed graphs for which the multipaths yield a matroid. We show that the family of MP-digraphs is closed under deletion and MP-contraction. We relate an evaluation of the Tutte polynomial of multipath matroids to certain digraph colourings. Finally, for MP-graphs whose underlying graph is a forest, we prove that the decategorification of multipath cohomology gives a specialisation of the Tutte polynomial – further linking path poset properties with combinatorial invariants of digraphs.
Authors
- Luigi Caputi (ORCID: https://orcid.org/0000-0002-6853-7651)
- Carlo Collari (ORCID: https://orcid.org/0000-0003-0034-0702)
- Sabino Di Trani (ORCID: https://orcid.org/0000-0002-6651-558X)
Institutions
- University of Pisa (IT)
- University of Bologna (IT)
Publication Details
- Journal
- Discrete Mathematics
- Published
- 2026-07-24
- DOI
- https://doi.org/10.1016/j.disc.2026.115320
- Primary Topic
- graph theory and CDMA systems
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Istituto Nazionale di Alta Matematica "Francesco Severi"
- Ministero dell’Istruzione, dell’Università e della Ricerca
- Università di Pisa
- Gruppo Nazionale per le Strutture Algebriche, Geometriche e le loro Applicazioni