O. V. Borodin, A. O. Ivanova, B. S. Stechkin, “Decomposing a planar graph into a forest and a subgraph of restricted maximum degree”, Сиб. электрон. матем. изв., 2007, том 4,страницы 296

Эта публикация цитируется в 3 статьях

Статьи

Decomposing a planar graph into a forest and a subgraph of restricted maximum degree

O. V. Borodin^a, A. O. Ivanova^b, B. S. Stechkin^c

^a Sobolev Institute of Mathematics, Novosibirsk, Russia
^b Yakutsk State University
^c Steklov's Institute of Mathematics, Moscow, Russia

Аннотация: We disprove the conjecture of He, Hou, Lih, Shao, Wang and Zhu that every plane graph $G$ can be edge-partitioned into a forest and a subgraph of the maximum degree at most $\lceil\Delta(G)/2\rceil+1$.

УДК: 519.172.2

MSC: 05C15

Поступила 16 июня 2007 г., опубликована 29 июня 2007 г.

Язык публикации: английский