The excessive [3]-index of all graphs

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 boolean OR(M is an element of M) M = E(G). G is called [m]-coverable if it has an [m]-covering. An [m]-covering M such that vertical bar M vertical bar 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 chi([m])' (G) (the value of chi([m])'(G) is conventionally set to infinity if G is not [m]-coverable). It is obvious that chi([1])'(G) = vertical bar E(G)vertical bar for every graph G, and it is not difficult to see that chi([2])'(G) = max{chi'(G), inverted right perpendicular vertical bar E(G)vertical bar/2inverted left perpendicular} for every [2]-coverable graph G. However the task of determining chi([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, there by determining the excessive [3]-index for all graphs.