Multipath matroids, digraph colourings, and the Tutte polynomial

Discrete Mathematics 2026 Open access

Read full text
Authors: Luigi Caputi, Carlo Collari, Sabino Di Trani
DOI: 10.1016/j.disc.2026.115320
Cited by: 0
References: 20

Abstract

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.

Fields of Study & Subjects

graph theory and CDMA systems Advanced Graph Theory Research Advanced Combinatorial Mathematics

Publication details

Journal / source
Discrete Mathematics
Publisher
Elsevier BV
Volume
349
Issue
12
Pages
115320–115320
Publication date
24 July 2026
Language
EN