Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Bul. Acad. Ştiinţe Repub. Mold. Mat.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, 2023, номер 3, страницы 26–36
DOI: https://doi.org/10.56415/basm.y2023.i3.p26
(Mi basm599)
 

Graphs, disjoint matchings and some inequalities

Lianna Hambardzumyana, Vahan Mkrtchyanb

a Department of Informatics and Applied Mathematics, Yerevan State University, Yerevan, 0025, Armenia
b Gran Sasso Science Institute, School of Advanced Studies, L'Aquila, Italy
Список литературы:
Аннотация: 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}$ [13]. 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.
Ключевые слова и фразы: bipartite graph, tree, unicyclic graph, edge-coloring, parsimonious edge-coloring.
Поступила в редакцию: 28.02.2020
Тип публикации: Статья
MSC: 05C15, 05C70
Образец цитирования: Lianna Hambardzumyan, Vahan Mkrtchyan, “Graphs, disjoint matchings and some inequalities”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 2023, № 3, 26–36
Цитирование в формате AMSBIB
\RBibitem{HamMkr23}
\by Lianna~Hambardzumyan, Vahan~Mkrtchyan
\paper Graphs, disjoint matchings and some inequalities
\jour Bul. Acad. \c Stiin\c te Repub. Mold. Mat.
\yr 2023
\issue 3
\pages 26--36
\mathnet{http://mi.mathnet.ru/basm599}
\crossref{https://doi.org/10.56415/basm.y2023.i3.p26}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/basm599
  • https://www.mathnet.ru/rus/basm/y2023/i3/p26
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
    Статистика просмотров:
    Страница аннотации:52
    PDF полного текста:11
    Список литературы:15
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024