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

Opuscula Mathematica

# 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.

Full text (pdf)

1. M.O. Albertson, R. Haas, Parsimonious edge coloring, Discrete Math. 148 (1996), 1-7.
2. M.O. Albertson, R. Haas, The edge chromatic difference sequence of a cubic graph, Discrete Math. 177 (1997), 1-8.
3. D. Aslanyan, V.V. Mkrtchyan, S.S. Petrosyan, G.N. Vardanyan, On disjoint matchings in cubic graphs: Maximum 2-edge-colorable and maximum 3-edge-colorable subgraphs, Discr. Appl. Math. 172 (2014), 12-27.
4. B. Bollobás, Extremal Graph Theory, Academic Press, London, New York, San Francisco, 1978.
5. A.D. Flaxman, S. Hoory, Maximum matchings in regular graphs of high girth, Electron. J. Combin. 14 (2007) 1, 1-4.
6. M.A. Henning, A. Yeo, Tight lower bounds on the size of a maximum matching in a regular graph, Graphs and Combinatorics 23 (2007) 6, 647-657.
7. A.M. Hobbs, E. Schmeichel, On the maximum number of independent edges in cubic graphs, Discrete Math. 42 (1982), 317-320.
8. I. Holyer, The NP-completeness of edge coloring, SIAM J. Comput. 10 (1981) 4, 718-720.
9. L. Lovász, Subgraphs with prescribed valencies, J. Comb. Theory 8 (1970), 391-416.
10. L. Lovász, M.D. Plummer, Matching theory, Ann. Discrete Math. 29 (1986).
11. V.V. Mkrtchyan, S.S. Petrosyan, G.N. Vardanyan, On disjoint matchings in cubic graphs, Discrete Math. 310 (2010), 1588-1613.
12. V.V. Mkrtchyan, E. Steffen, Maximum $$\Delta$$-edge-colorable subgraphs of class II graphs, J. Graph Theory 4 (2012), 473-482.
13. T. Nishizeki, On the maximum matchings of regular multigraphs, Discrete Math. 37 (1981), 105-114.
14. T. Nishizeki, I. Baybars, Lower bounds on the cardinality of the maximum matchings of planar graphs, Discrete Math. 28 (1979), 255-267.
15. R. Rizzi, Approximating the maximum 3-edge-colorable subgraph problem, Discrete Math. 309 (2009), 4166-4170.
16. C.E. Shannon, A theorem on coloring the lines of a network, J. Math. and Phys. 28 (1949), 148-151.
17. E. Steffen, Measurements of edge-uncolorability, Discrete Math. 280 (2004), 191-214.
18. C. Thomassen, A remark on the factor theorems of Lovász and Tutte, J. Graph Theory 5 (1981), 441-442.
19. V.G. Vizing, The chromatic class of a multigraph, Kibernetika 3 (1965), 29-39 [in Russian].
20. J. Weinstein, Large matchings in graphs, Canadian J. Math. 26 (1974) 6, 1498-1508.
21. D.B. West, Introduction to Graph Theory, Prentice-Hall, Englewood Cliffs, 1996.
22. Q.R. Yu, G. Liu, Graph Factors and Matching Extensions, Springer, 2009.
• Vahan V. Mkrtchyan
• Yerevan State University, Department of Informatics and Applied Mathematics, Yerevan, 0025, Armenia
• National Academy of Sciences of Republic of Armenia, Institute for Informatics and Automation Problems, 0014, Armenia
• Gagik N. Vardanyan
• Yerevan State University, Department of Informatics and Applied Mathematics, Yerevan, 0025, Armenia
• Communicated by Mariusz Meszka.
• Revised: 2016-09-15.
• Accepted: 2016-09-29.
• Published online: 2017-01-30.