The excessive [m]-index of a graph G, denoted by χ′[m](G), is the minimum number of matchings of size m needed to cover the edge-set of G. We set χ′[m](G) = ∞ if such a cover does not exist and we call a graph G[m]-coverable if its excessive [m]-index is finite. Obviously χ′[1](G) = |E(G)| and it is easy to prove for a [2]-coverable graph G that χ′[2](G) = max {χ′(G), ⌈|E(G)|/2⌉} holds, where χ′(G) denotes the chromatic index of G. The case m = 3 is completely solved in Cariolaro and Fu (2009) [4]. In this paper we prove a general formula for computing the excessive [4]-index of a tree and we conjecture a possible generalization for any value of m. Furthermore, we prove that such a formula does not work for the excessive [4]-index of an arbitrary graph.
On the excessive [m]-index of a tree
Mazzuoccolo, Giuseppe
2014-01-01
Abstract
The excessive [m]-index of a graph G, denoted by χ′[m](G), is the minimum number of matchings of size m needed to cover the edge-set of G. We set χ′[m](G) = ∞ if such a cover does not exist and we call a graph G[m]-coverable if its excessive [m]-index is finite. Obviously χ′[1](G) = |E(G)| and it is easy to prove for a [2]-coverable graph G that χ′[2](G) = max {χ′(G), ⌈|E(G)|/2⌉} holds, where χ′(G) denotes the chromatic index of G. The case m = 3 is completely solved in Cariolaro and Fu (2009) [4]. In this paper we prove a general formula for computing the excessive [4]-index of a tree and we conjecture a possible generalization for any value of m. Furthermore, we prove that such a formula does not work for the excessive [4]-index of an arbitrary graph.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
