RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2009, том 6, страницы 13–16 (Mi semr53)

Эта публикация цитируется в 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.

УДК: 519.172.2

MSC: 05C15

Поступила 11 января 2009 г., опубликована 26 января 2009 г.



Реферативные базы данных:


© МИАН, 2024