✦ LIBER ✦
Surfaces, Tree-Width, Clique-Minors, and Partitions
✍ Scribed by Guoli Ding; Bogdan Oporowski; Daniel P. Sanders; Dirk Vertigan
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 214 KB
- Volume
- 79
- Category
- Article
- ISSN
- 0095-8956
No coin nor oath required. For personal study only.
✦ Synopsis
In 1971, Chartrand, Geller, and Hedetniemi conjectured that the edge set of a planar graph may be partitioned into two subsets, each of which induces an outerplanar graph. Some partial results towards this conjecture are presented. One such result, in which a planar graph may be thus edge partitioned into two series-parallel graphs, has nice generalizations for graphs embedded onto an arbitrary surface and graphs with no large clique-minor. Several open questions are raised. 2000