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

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

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

УДК: 519.172.2

MSC: 05C15

Поступила 30 октября 2007 г., опубликована 8 ноября 2007 г.



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


© МИАН, 2024