TY  - JOUR
ID  - Mkrtchyan2017
LB  - Mkrtchyan2017
AU  - Mkrtchyan, Vahan V.
AU  - Vardanyan, Gagik N.
TI  - On strongly spanning k-edge-colorable subgraphs
ST  - On strongly spanning k-edge-colorable subgraphs
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2017
VL  - 37
IS  - 3
SP  - 435
EP  - 446
DO  - http://dx.doi.org/10.7494/OpMath.2017.37.3.435
UR  - http://dx.doi.org/10.7494/OpMath.2017.37.3.435
AB  - 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.
KW  - \(k\)-edge-colorable subgraph
KW  - maximum \(k\)-edge-colorable subgraph
KW  - strongly spanning \(k\)-edge-colorable subgraph
KW  - \([1,k]\)-factor
SN  - 1232-9274
ER  -