Excessive [ l, m ] -factorizations

David Cariolaro, Giuseppe Mazzuoccolo*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Given two positive integers l and m, with l≤m, an [l,m]-covering of a graph G is a set M of matchings of G whose union is the edge set of G and such that l≤;|M|≤m for every MεM. An [l,m]-covering M of G is an excessive [l,m]-factorization of G if the cardinality of M is as small as possible. The number of matchings in an excessive [l,m]-factorization of G (or ∞, if G does not admit an excessive [l,m]-factorization) is a graph parameter called the excessive [l,m]-index of G and denoted by χ[l,m]′(G). In this paper we study such parameter. Our main result is a general formula for the excessive [l,m]-index of a graph G in terms of other graph parameters. Furthermore, we give a polynomial time algorithm which computes χ[l,m]′(G) for any fixed constants l and m and outputs an excessive [l,m]-factorization of G, whenever the latter exists.

Original languageEnglish
Pages (from-to)1917-1927
Number of pages11
JournalDiscrete Mathematics
Issue number11
Publication statusPublished - 6 Jun 2015
Externally publishedYes


  • Chromatic index
  • Excessive [ l m ] -factorization
  • Excessive [ l m ] -index
  • Matching


Dive into the research topics of 'Excessive [ l, m ] -factorizations'. Together they form a unique fingerprint.

Cite this