On strongly spanning k-edge-colorable subgraphs
Vahan V. Mkrtchyan
Gagik N. Vardanyan
Abstract. A subgraph \(H\) of a multigraph \(G\) is called strongly spanning, if any vertex of \(G\) is not isolated in \(H\). \(H\) is called maximum \(k\)-edge-colorable, if \(H\) is proper \(k\)-edge-colorable and has the largest size. We introduce a graph-parameter \(sp(G)\), that coincides with the smallest \(k\) for which a multigraph \(G\) has a maximum \(k\)-edge-colorable subgraph that is strongly spanning. Our first result offers some alternative definitions of \(sp(G)\). Next, we show that \(\Delta(G)\) is an upper bound for \(sp(G)\), and then we characterize the class of multigraphs \(G\) that satisfy \(sp(G)=\Delta(G)\). Finally, we prove some bounds for \(sp(G)\) that involve well-known graph-theoretic parameters.
Keywords: \(k\)-edge-colorable subgraph, maximum \(k\)-edge-colorable subgraph, strongly spanning \(k\)-edge-colorable subgraph, \([1,k]\)-factor.
Mathematics Subject Classification: 05C70, 05C15.