|
Сибирские электронные математические известия, 2009, том 6, страницы 13–16
(Mi semr53)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Статьи
Разбиение разреженных плоских графов на два подграфа малой степени
О. В. Бородинa, А. О. Ивановаb a Институт математики им. С. Л. Соболева СО РАН
b НИИ математики при Якутском госуниверситете
Аннотация:
A graph $G$ is said to be $(a,b)$-partitionable for positive integers $a$, $b$ if its vertices can be partitioned into subsets $V_1$ and $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. We prove that every planar graph of girth $8$ is $(2,2)$-partitionable.
Ключевые слова:
planar graph, coloring, vertex partition.
Поступила 11 января 2009 г., опубликована 26 января 2009 г.
Образец цитирования:
О. В. Бородин, А. О. Иванова, “Разбиение разреженных плоских графов на два подграфа малой степени”, Сиб. электрон. матем. изв., 6 (2009), 13–16
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr53 https://www.mathnet.ru/rus/semr/v6/p13
|
Статистика просмотров: |
Страница аннотации: | 415 | PDF полного текста: | 82 | Список литературы: | 73 |
|