Opuscula Math. 37, no. 3 (2017), 435-446

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.
  • Received: 2015-12-03.
  • Revised: 2016-09-15.
  • Accepted: 2016-09-29.
  • Published online: 2017-01-30.
Opuscula Mathematica - cover

Cite this article as:
Vahan V. Mkrtchyan, Gagik N. Vardanyan, On strongly spanning k-edge-colorable subgraphs, Opuscula Math. 37, no. 3 (2017), 435-446, http://dx.doi.org/10.7494/OpMath.2017.37.3.435

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.