O. V. Borodin, A. O. Ivanova, B. S. Stechkin, “Decomposing a planar graph into a forest and a subgraph of restricted maximum degree”, Sib. Èlektron. Mat. Izv., 2007, Volume 4,Pages <nobr>296

This article is cited in 3 papers

Research papers

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

Abstract: 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$.

UDC: 519.172.2

MSC: 05C15

Received June 16, 2007, published June 29, 2007

Language: English