The excessive [3]-index of all graphs (Q2380288)

Summary: Let \(m\) be a positive integer and let \(G\) be a graph. A set \({\mathcal M}\) of matchings of \(G\), all of which of size \(m\), is called an \([m]\)-covering of \(G\) if \(\bigcup_{M\in{\mathcal M}}M= E(G)\). \(G\) is called \([m]\)-coverable if it has an \([m]\)-covering. An \([m]\)-covering \({\mathcal M}\) such that \(|{\mathcal 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 \(\chi_{[m]}'(G)\) (the value of \(\chi_{[m]}'(G)\) is conventionally set to \(\infty\) if \(G\) is not \([m]\)-coverable). It is obvious that \(\chi_{[1]}'(G)= |E(G)|\) for every graph \(G\), and it is not difficult to see that \(\chi_{[2]}'(G)= max\{\chi'(G), \lceil|E(G)|/2\rceil\}\) 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\geq 3\) is unknown. In this paper we determine such a formula for \(m=3\), thereby determining the excessive [3]-index for all graphs.