On strongly spanning k-edge-colorable subgraphs

• Autorzy: Mkrtchyan V. V. , Vardanyan G. N.

Identyfikatory

DOI

10.7494/OpMath.2017.37.3.435

• Języki publikacji: EN

Abstrakty

EN

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 Δ (G) is an upper bound for sp(G), and then we characterize the class of multigraphs G that satisfy sp(G) = Δ (G). Finally, we prove some bounds for sp(G) that involve well-known graph-theoretic parameters.

Słowa kluczowe

EN

k-edge-colorable subgraph; maximum k-edge-colorable subgraph; trongly spanning k-edge-colorable subgraph; [1, k]-factor.

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2017
• Tom: Vol. 37, no. 3
• Strony: 447--456
• Opis fizyczny: Bibliogr. 22 poz.

Twórcy

autor

Mkrtchyan V. V.

• Yerevan State University Department of Informatics and Applied Mathematics Yerevan, 0025, Armenia

autor

Vardanyan G. N.

• Yerevan State University Department of Informatics and Applied Mathematics Yerevan, 0025, Armenia

Bibliografia

• [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 -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.

Uwagi

EN

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).