|
|
Сиб. электрон. матем. изв., 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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
О. В. Бородин, А. О. Иванова, “Почти правильные 2-раскраски вершин разреженных графов”, Дискретн. анализ и исслед. опер., 16:2 (2009), 16–20
 ; O. V. Borodin, A. O. Ivanova, “Near-proper vertex 2-colorings of sparse graphs”, J. Appl. Industr. Math., 4:1 (2010), 21–23  -
Д. Ж. Замбалаева, “Разбиение плоского графа с обхватом 7 на два звёздных леса”, Дискретн. анализ и исслед. опер., 16:3 (2009), 20–46
-
О. В. Бородин, А. О. Иванова, “Разбиение разреженных плоских графов на два подграфа малой степени”, Сиб. электрон. матем. изв., 6 (2009), 13–16
-
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
  -
Borodin O.V., Ivanova A.O., “List Strong Linear 2-Arboricity of Sparse Graphs”, J. Graph Theory, 67:2 (2011), 83–90
-
О. В. Бородин, А. В. Косточка, “Вершинные разбиения разреженных графов на независимое множество и подграф максимальной степени не более $1$”, Сиб. матем. журн., 52:5 (2011), 1004–1010 ; 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
-
Borodin O.V., Ivanova A.O., Montassier M., Raspaud A., “$(k,j)$-coloring of sparse graphs”, Discrete Appl. Math., 159:17 (2011), 1947–1953
-
Borodin O.V., Ivanova A.O., Montassier M., Raspaud A., “$(k,1)$-coloring of sparse graphs”, Discrete Math., 312:6 (2012), 1128–1135
-
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
-
Borodin O.V., Kostochka A., Yancey M., “On 1-Improper 2-Coloring of Sparse Graphs”, Discrete Math., 313:22 (2013), 2638–2649
-
А. Н. Глебов, Д. Ж. Замбалаева, “Разбиение плоского графа с обхватом 6 на два леса с длиной цепей не больше 4”, Дискретн. анализ и исслед. опер., 21:2 (2014), 33–51 ; 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
-
Dorbec P., Kaiser T., Montassier M., Raspaud A., “Limits of Near-Coloring of Sparse Graphs”, J. Graph Theory, 75:2 (2014), 191–202
-
Borodin O.V., Kostochka A.V., “Defective 2-Colorings of Sparse Graphs”, J. Comb. Theory Ser. B, 104 (2014), 72–80
-
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
-
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
 -
А. Н. Глебов, Д. Ж. Замбалаева, “Путевая разбиваемость планарных графов обхвата 4 без смежных коротких циклов”, Сиб. электрон. матем. изв., 15 (2018), 1040–1047
|
| Просмотров: |
| Эта страница: | 276 | | Полный текст: | 56 | | Литература: | 39 |
|
Пользовательское соглашение