On the Complexity of Computing the Excessive [B]-Index of a Graph

David Cariolaro, Romeo Rizzi

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Let B be a positive integer and let G be a simple graph. An excessive [B]-factorization of G is a minimum set of matchings, each of size B, whose union is E(G). The number of matchings in an excessive [B]-factorization of G (or ∞ if an excessive [B]-factorization does not exist) is a graph parameter called the excessive [B]-index of G and denoted by χ[B]′(G). In this article we prove that, for any fixed value of B, the parameter χ[B]′(G) can be computed in polynomial time in the size of the graph G. This solves a problem posed by one of the authors at the 21st British Combinatorial Conference.

Original languageEnglish
Pages (from-to)65-74
Number of pages10
JournalJournal of Graph Theory
Volume82
Issue number1
DOIs
Publication statusPublished - 1 May 2016
Externally publishedYes

Keywords

  • chromatic index
  • excessive [B]-factorization
  • excessive [B]-index
  • matching

Fingerprint

Dive into the research topics of 'On the Complexity of Computing the Excessive [B]-Index of a Graph'. Together they form a unique fingerprint.

Cite this