Opuscula Math. 37, no. 3 (), 435-446
http://dx.doi.org/10.7494/OpMath.2017.37.3.435
Opuscula Mathematica

# On strongly spanning k-edge-colorable subgraphs

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.