Geodesic
Graphs, Disjoint Matchings and Some Inequalities
Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 3 (2023), pp. 26-36.

Voir la notice de l'article provenant de la source Math-Net.Ru

A graph $G$ is $k$-edge-colorable if the edges of $G$ can be assigned a color from $\{1,...,k\}$ so that adjacent edges of $G$ receive different colors. A maximum $k$-edge-colorable subgraph of $G$ is a $k$-edge-colorable subgraph of $G$ containing maximum number of edges. For $k \geq 1$ and a graph $G$, let $\nu_k(G)$ denote the number of edges in a maximum $k$-edge-colorable subgraph of $G$. In 2010 Mkrtchyan, Petrosyan and Vardanyan proved that if $G$ is a cubic graph, then $\nu_2(G) \leq \frac{|V(G)| + 2\cdot \nu_3(G)}{4}$ [samvel:2010]. For cubic graphs containing a perfect matching, in particular, for bridgeless cubic graphs, this inequality can be stated as $\nu_2(G) \leq \frac{\nu_1(G) + \nu_3(G)}{2}$. One may wonder whether there are other well-known graph classes, where a similar result can be obtained. In this work, we prove lower bounds for $\nu_k(G)$ in terms of $\frac{\nu_{k-1}(G)+\nu_{k+1}(G)}{2}$ for $k\geq 2$ and graphs $G$ containing at most $1$ cycle. We also present the corresponding conjectures for nearly bipartite graphs. 
@article{BASM_2023_3_a1,
     author = {Lianna Hambardzumyan and Vahan Mkrtchyan},
     title = {Graphs, {Disjoint} {Matchings} and {Some} {Inequalities}},
     journal = {Buletinul Academiei de \c{S}tiin\c{t}e a Republicii Moldova. Matematica},
     pages = {26--36},
     publisher = {mathdoc},
     number = {3},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/BASM_2023_3_a1/}
}
TY  - JOUR
AU  - Lianna Hambardzumyan
AU  - Vahan Mkrtchyan
TI  - Graphs, Disjoint Matchings and Some Inequalities
JO  - Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
PY  - 2023
SP  - 26
EP  - 36
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BASM_2023_3_a1/
LA  - ru
ID  - BASM_2023_3_a1
ER  - 
%0 Journal Article
%A Lianna Hambardzumyan
%A Vahan Mkrtchyan
%T Graphs, Disjoint Matchings and Some Inequalities
%J Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
%D 2023
%P 26-36
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BASM_2023_3_a1/
%G ru
%F BASM_2023_3_a1
Lianna Hambardzumyan; Vahan Mkrtchyan. Graphs, Disjoint Matchings and Some Inequalities. Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 3 (2023), pp. 26-36. http://geodesic.mathdoc.fr/item/BASM_2023_3_a1/

[1] M. Albertson and R. Haas, “Parsimonious edge coloring”, Discrete Math., 148 (1996), 1–7 | DOI | MR | Zbl

[2] M. Albertson and R. Haas, “The edge chromatic difference sequence of a cubic graph”, Discrete Math., 177 (1997), 1–8 | DOI | MR | Zbl

[3] D. Aslanyan, V. Mkrtchyan, S. Petrosyan, and G. Vardanyan, “On disjoint matchings in cubic graphs: Maximum 2-edge-colorable and maximum 3-edge-colorable subgraphs”, Discrete Appl. Math., 172 (2014), 12–27 | DOI | MR | Zbl

[4] B. Bollobas, Extremal Graph Theory, Academic Press, London–New York–San Francisco, 1978 | MR | Zbl

[5] A. Cavicchioli, M. Meschiari, B. Ruini, and F. Spaggiari, “A survey on snarks and new results: Products, reducibility and a computer search”, J. Graph Theory, 28:2 (1998), 57–86 | 3.0.CO;2-D class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[6] A. D. Flaxman and S. Hoory, “Maximum matchings in regular graphs of high girth”, Electron. J. Combin., 14:1 (2007), 1–4 | MR

[7] J.-L. Fouquet and J.-M. Vanherpe, “On parsimonious edge-colouring of graphs with maximum degree three”, Graphs Combin., 29:3 (2013), 475–487 | DOI | MR | Zbl

[8] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969 | MR | Zbl

[9] M. A. Henning and A. Yeo, “Tight lower bounds on the size of a maximum matching in a regular graph”, Graphs Combin., 23:6 (2007), 647–657 | DOI | MR | Zbl

[10] S. il Oum, “Perfect matchings in claw-free cubic graphs”, Electron. J. Combin., 18:1, P62 | DOI | MR | Zbl

[11] M. J. Kaminski and L. Kowalik, “Beyond the Vizing's bound for at most seven colors”, SIAM J. Discrete Math., 28:3 (2014), 1334–1362 | DOI | MR | Zbl

[12] L. Karapetyan, V.V. Mkrtchyan, “On maximum $k$-edge-colorable subgraphs of bipartite graphs”, Discrete Appl. Math., 257:31 (2019), 226–232 | DOI | MR | Zbl

[13] V. Mkrtchyan, S. Petrosyan, and G. Vardanyan, “On disjoint matchings in cubic graphs”, Discrete Math., 310 (2010), 1588–1613 | DOI | MR | Zbl

[14] T. Nishizeki, “On the maximum matchings of regular multigraphs”, Discrete Math., 37 (1981), 105–114 | DOI | MR | Zbl

[15] T. Nishizeki and I. Baybars, “Lower bounds on the cardinality of the maximum matchings of planar graphs”, Discrete Math., 28 (1979), 255–267 | DOI | MR | Zbl

[16] R. Rizzi, “Approximating the maximum 3-edge-colorable subgraph problem”, Discrete Math., 309:12 (2009), 4166–4170 | DOI | MR | Zbl

[17] C. E. Shannon, “A theorem on coloring the lines of a network”, J. Math. Phys., 28 (1949), 148–151 | DOI | MR | Zbl

[18] E. Steffen, “Classifications and characterizations of snarks”, Discrete Math., 188 (1998), 183–203 | DOI | MR | Zbl

[19] E. Steffen, “Measurements of edge-uncolorability”, Discrete Math., 280 (2004), 191–214 | DOI | MR | Zbl

[20] M. Stiebitz, D. Scheide, B. Toft, and L. M. Favrholdt, Graph Edge Coloring, John Wiley and Sons, 2012 | MR | Zbl

[21] D. P. Sumner, “Graphs with 1-factors”, Proc. Amer. Math. Soc., 42 (1974), 8–12 | DOI | MR | Zbl

[22] V. Vizing, “On an estimate of the chromatic class of a $p$-graph”, Discret Analiz, 3 (1964), 25–30 | MR

[23] J. Weinstein, “Large matchings in graphs”, Canad. J. Math., 26:6 (1974), 1498–1508 | DOI | MR | Zbl

[24] D. West, Introduction to Graph Theory, Prentice-Hall, Englewood Cliffs, 1996 | Zbl