## Abstract

Let m be a positive integer and let G be a graph. A set M of matchings of G, all of which of size m, is called an [m]-covering of G if U_{M} = E(G). G is called [m]-coverable if it has an [m]-covering. An [m]-covering M such that |M| is minimum is called an excessive [m]-factorization of G and the number of matchings it contains is a graph parameter called excessive [m]-index and denoted by x́ [m](G) (the value of x́ [m](G) is conventionally set to x́ if G is not [m]-coverable). It is obvious that x́ [1](G) = |E(G)| for every graph G, and it is not difficult to see that x́ [2](G) = max{x́(G), x́|E(G)|/2x́} for every [2]-coverable graph G. However the task of determining x́ [m](G) for arbitrary m and G seems to increase very rapidly in difficulty as m increases, and a general formula for m≥ 3 is unknown. In this paper we determine such a formula for m = 3, thereby determining the excessive [3]-index for all graphs.

Original language | English |
---|---|

Article number | R124 |

Journal | Electronic Journal of Combinatorics |

Volume | 16 |

Issue number | 1 |

DOIs | |

Publication status | Published - 5 Oct 2009 |

## Keywords

- Edge coloring
- Excessive [m]-factorization
- Excessive [m]-index
- Matching