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

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

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



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






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


Сиб. электрон. матем. изв., 2007, том 4, страницы 450–459 (Mi semr167)  

Эта публикация цитируется в 16 научных статьях (всего в 16 статьях)

Статьи

Путевые разбиения планарных графов

А. Н. Глебовa, Д. Ж. Замбалаеваb

a Институт математики им. С. Л. Соболева СО РАН
b Новосибирский государственный университет

Аннотация: A graph $G$ is said to be $(a,b)$-partitionable for positive intergers $a,b$ if its vertices can be partitioned into subsets $V_1,V_2$ such that in $G[V_1]$ any path contains at most $a$ vertices and in $G[V_2]$ any path contains at most $b$ vertices. Graph $G$ is $\tau$-partitionable if it is $(a,b)$-partitionable for any $a,b$ such that $a+b$ is the number of vertices in the longest path of $G$. We prove that every planar graph of girth $5$ is $\tau$-partitionable and that planar graphs with girth $8$, $9$ and $16$ are $(2,3)$-, $(2,2)$- and $(1,2)$-partitionable respectively.

Полный текст: PDF файл (736 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:
Тип публикации: Статья
УДК: 519.172.2
MSC: 05C15
Поступила 30 октября 2007 г., опубликована 8 ноября 2007 г.

Образец цитирования: А. Н. Глебов, Д. Ж. Замбалаева, “Путевые разбиения планарных графов”, Сиб. электрон. матем. изв., 4 (2007), 450–459

Цитирование в формате AMSBIB
\RBibitem{GleZam07}
\by А.~Н.~Глебов, Д.~Ж.~Замбалаева
\paper Путевые разбиения планарных графов
\jour Сиб. электрон. матем. изв.
\yr 2007
\vol 4
\pages 450--459
\mathnet{http://mi.mathnet.ru/semr167}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2465436}
\zmath{https://zbmath.org/?q=an:1132.05315}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/semr167
  • http://mi.mathnet.ru/rus/semr/v4/p450

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. О. В. Бородин, А. О. Иванова, “Почти правильные 2-раскраски вершин разреженных графов”, Дискретн. анализ и исслед. опер., 16:2 (2009), 16–20  mathnet  mathscinet  zmath; O. V. Borodin, A. O. Ivanova, “Near-proper vertex 2-colorings of sparse graphs”, J. Appl. Industr. Math., 4:1 (2010), 21–23  crossref
    2. Д. Ж. Замбалаева, “Разбиение плоского графа с обхватом 7 на два звёздных леса”, Дискретн. анализ и исслед. опер., 16:3 (2009), 20–46  mathnet  mathscinet  zmath
    3. О. В. Бородин, А. О. Иванова, “Разбиение разреженных плоских графов на два подграфа малой степени”, Сиб. электрон. матем. изв., 6 (2009), 13–16  mathnet  mathscinet
    4. Borodin O.V., Ivanova A.O., Montassier M., Ochem P., Raspaud A., “Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most $k$”, J. Graph Theory, 65:2 (2010), 83–93  crossref  mathscinet  zmath  isi  elib
    5. Borodin O.V., Ivanova A.O., “List Strong Linear 2-Arboricity of Sparse Graphs”, J. Graph Theory, 67:2 (2011), 83–90  crossref  mathscinet  zmath  isi  elib
    6. О. В. Бородин, А. В. Косточка, “Вершинные разбиения разреженных графов на независимое множество и подграф максимальной степени не более $1$”, Сиб. матем. журн., 52:5 (2011), 1004–1010  mathnet  mathscinet; O. V. Borodin, A. V. Kostochka, “Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most $1$”, Siberian Math. J., 52:5 (2011), 796–801  crossref  isi
    7. Borodin O.V., Ivanova A.O., Montassier M., Raspaud A., “$(k,j)$-coloring of sparse graphs”, Discrete Appl. Math., 159:17 (2011), 1947–1953  crossref  mathscinet  zmath  isi  elib
    8. Borodin O.V., Ivanova A.O., Montassier M., Raspaud A., “$(k,1)$-coloring of sparse graphs”, Discrete Math., 312:6 (2012), 1128–1135  crossref  mathscinet  zmath  isi  elib
    9. Esperet L., Montassier M., Ochem P., Pinlou A., “A Complexity Dichotomy for the Coloring of Sparse Graphs”, J. Graph Theory, 73:1 (2013), 85–102  crossref  mathscinet  zmath  isi  elib
    10. Borodin O.V., Kostochka A., Yancey M., “On 1-Improper 2-Coloring of Sparse Graphs”, Discrete Math., 313:22 (2013), 2638–2649  crossref  mathscinet  zmath  isi  elib
    11. А. Н. Глебов, Д. Ж. Замбалаева, “Разбиение плоского графа с обхватом 6 на два леса с длиной цепей не больше 4”, Дискретн. анализ и исслед. опер., 21:2 (2014), 33–51  mathnet  mathscinet; A. N. Glebov, D. Zh. Zambalaeva, “A partition of a planar graph with girth 6 into two forests containing no path of length greater than 4”, J. Appl. Industr. Math., 8:3 (2014), 317–328  crossref
    12. Dorbec P., Kaiser T., Montassier M., Raspaud A., “Limits of Near-Coloring of Sparse Graphs”, J. Graph Theory, 75:2 (2014), 191–202  crossref  mathscinet  zmath  isi  elib
    13. Borodin O.V., Kostochka A.V., “Defective 2-Colorings of Sparse Graphs”, J. Comb. Theory Ser. B, 104 (2014), 72–80  crossref  mathscinet  zmath  isi  elib
    14. Kim J., Kostochka A., Zhu X., “Improper Coloring of Sparse Graphs With a Given Girth, i: (0,1)-Colorings of Triangle-Free Graphs”, Eur. J. Comb., 42 (2014), 26–48  crossref  mathscinet  zmath  isi  elib
    15. Choi H., Choi I., Jeong J., Suh G., “(1, K)-Coloring of Graphs With Girth At Least Five on a Surface”, J. Graph Theory, 84:4 (2017), 521–535  crossref  mathscinet  zmath  isi  scopus
    16. А. Н. Глебов, Д. Ж. Замбалаева, “Путевая разбиваемость планарных графов обхвата 4 без смежных коротких циклов”, Сиб. электрон. матем. изв., 15 (2018), 1040–1047  mathnet  crossref
  • Просмотров:
    Эта страница:276
    Полный текст:56
    Литература:39
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021