Authors
Citation
C. Thomassen, DECOMPOSING A PLANAR GRAPH INTO DEGENERATE GRAPHS, J COMB TH B, 65(2), 1995, pp. 305-314
Citations number
12
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956
→ ACNP
Volume
65
Issue
2
Year of publication
1995
Pages
305 - 314
Database
ISI
SICI code
0095-8956(1995)65:2<305:DAPGID>2.0.ZU;2-P
Abstract
We prove the conjecture made by O. V. Borodin in 1976 that the vertex
set of any planar graph can be decomposed into two sets such that one
of them induces a 3-degenerate graph and the other induces a 2-degener
ate graph, that is, a forest. (C) 1995 Academic Press, Inc.