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.
- M.O. Albertson, R. Haas, Parsimonious edge coloring, Discrete Math. 148 (1996), 1-7.
- M.O. Albertson, R. Haas, The edge chromatic difference sequence of a cubic graph, Discrete Math. 177 (1997), 1-8.
- 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.
- B. Bollobás, Extremal Graph Theory, Academic Press, London, New York, San Francisco, 1978.
- A.D. Flaxman, S. Hoory, Maximum matchings in regular graphs of high girth, Electron. J. Combin. 14 (2007) 1, 1-4.
- 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.
- A.M. Hobbs, E. Schmeichel, On the maximum number of independent edges in cubic graphs, Discrete Math. 42 (1982), 317-320.
- I. Holyer, The NP-completeness of edge coloring, SIAM J. Comput. 10 (1981) 4, 718-720.
- L. Lovász, Subgraphs with prescribed valencies, J. Comb. Theory 8 (1970), 391-416.
- L. Lovász, M.D. Plummer, Matching theory, Ann. Discrete Math. 29 (1986).
- V.V. Mkrtchyan, S.S. Petrosyan, G.N. Vardanyan, On disjoint matchings in cubic graphs, Discrete Math. 310 (2010), 1588-1613.
- V.V. Mkrtchyan, E. Steffen, Maximum \(\Delta\)-edge-colorable subgraphs of class II graphs, J. Graph Theory 4 (2012), 473-482.
- T. Nishizeki, On the maximum matchings of regular multigraphs, Discrete Math. 37 (1981), 105-114.
- T. Nishizeki, I. Baybars, Lower bounds on the cardinality of the maximum matchings of planar graphs, Discrete Math. 28 (1979), 255-267.
- R. Rizzi, Approximating the maximum 3-edge-colorable subgraph problem, Discrete Math. 309 (2009), 4166-4170.
- C.E. Shannon, A theorem on coloring the lines of a network, J. Math. and Phys. 28 (1949), 148-151.
- E. Steffen, Measurements of edge-uncolorability, Discrete Math. 280 (2004), 191-214.
- C. Thomassen, A remark on the factor theorems of Lovász and Tutte, J. Graph Theory 5 (1981), 441-442.
- V.G. Vizing, The chromatic class of a multigraph, Kibernetika 3 (1965), 29-39 [in Russian].
- J. Weinstein, Large matchings in graphs, Canadian J. Math. 26 (1974) 6, 1498-1508.
- D.B. West, Introduction to Graph Theory, Prentice-Hall, Englewood Cliffs, 1996.
- 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.
- Received: 2015-12-03.
- Revised: 2016-09-15.
- Accepted: 2016-09-29.
- Published online: 2017-01-30.
