|
Сибирские электронные математические известия, 2007, том 4, страницы 450–459
(Mi semr167)
|
|
|
|
Эта публикация цитируется в 17 научных статьях (всего в 17 статьях)
Статьи
Путевые разбиения планарных графов
А. Н. Глебов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.
Поступила 30 октября 2007 г., опубликована 8 ноября 2007 г.
Образец цитирования:
А. Н. Глебов, Д. Ж. Замбалаева, “Путевые разбиения планарных графов”, Сиб. электрон. матем. изв., 4 (2007), 450–459
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr167 https://www.mathnet.ru/rus/semr/v4/p450
|
Статистика просмотров: |
Страница аннотации: | 423 | PDF полного текста: | 94 | Список литературы: | 66 |
|