Сибирские электронные математические известия
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

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

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



Сиб. электрон. матем. изв.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Сибирские электронные математические известия, 2021, том 18, выпуск 2, страницы 975–984
DOI: https://doi.org/10.33048/semi.2021.18.073
(Mi semr1414)
 

Дискретная математика и математическая кибернетика

Путевая разбиваемость планарных графов с ограничениями на расположение коротких циклов

А. Н. Глебов

Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
Список литературы:
Аннотация: Let $a$ and $b$ be positive intergers. An $(a,b)$-partition of a graph is a partition of its vertex set into two subsets so that in the subgraph induced by the first subset each path contains at most $a$ vertices while in the subgraph induced by the second subset each path contains at most $b$ vertices. A graph $G$ is $\tau$-partitionable if it has an $(a,b)$-partition for any pair $a,b$ such that $a+b$ equals to the number of vertices in the longest path in $G$. The celebrated Path Partition Conjecture of Lovász and Mihók ($1981$) states that every graph is $\tau$-partitionable. In $2018$, Glebov and Zambalaeva proved the Conjecture for triangle-free planar graphs where cycles of length $4$ have no common edges with cycles of length $4$ and $5$. The purpose of this paper is to generalize this result by proving that every planar graph in which cycles of length $4$ to $7$ have no chords while $3$-cycles have no common vertices with cycles of length $3$ and $4$ is $\tau$-partitionable.
Ключевые слова: graph, planar graph, girth, path partition, $\tau$-partitionable graph, Path Partition Conjecture.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 18-01-00353_а
18-01-00747_а
Работа поддержана Российским фондом фундаментальных исследований (проекты 18-01-00353 и 18-01-00747).
Поступила 15 ноября 2020 г., опубликована 15 сентября 2021 г.
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.172.2, 519.174
MSC: 05C10, 05C15, 05C70
Образец цитирования: А. Н. Глебов, “Путевая разбиваемость планарных графов с ограничениями на расположение коротких циклов”, Сиб. электрон. матем. изв., 18:2 (2021), 975–984
Цитирование в формате AMSBIB
\RBibitem{Gle21}
\by А.~Н.~Глебов
\paper Путевая разбиваемость планарных графов с ограничениями на расположение коротких циклов
\jour Сиб. электрон. матем. изв.
\yr 2021
\vol 18
\issue 2
\pages 975--984
\mathnet{http://mi.mathnet.ru/semr1414}
\crossref{https://doi.org/10.33048/semi.2021.18.073}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/semr1414
  • https://www.mathnet.ru/rus/semr/v18/i2/p975
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024