The excessive [3]-index of all graphs
edge coloringexcessive \([m\)-factorization]excessive \([m\)-index]matching
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.
- Excessive \([l, m]\)-factorizations
- Berge-Fulkerson conjecture on certain snarks
- On the complexity of computing the excessive \([B]\)-index of a graph
- On excessive index of certain networks
- Excessive index for mesh derived networks
- Some results of minimum sets of 1-factors covering a graph
- Excessive factorizations of bipartite multigraphs
- Graphs of arbitrary excessive class
- On the excessive \([m]\)-index of a tree
- Covering graphs with matchings of fixed size
This page was built for publication: The excessive [3]-index of all graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380288)
