Partitioning into two graphs with only small components
by
Bogdan Oporowski
Louisiana State University
Coauthors: Noga Alon (Tel Aviv University), Guoli Ding (Louisiana State University), Dirk Vertigan (Louisiana State University)

The talk presents several results on edge partitions and vertex partitions of graphs into two graphs with bounded size components. We show that every graph of bounded tree-width and bounded maximum degree admits such partitions. We also show that an arbitrary graph of maximum degree four has a vertex partition into two graphs each of which has only components on at most 57 vertices. It is not known whether a similar result holds for maximum degree five, but no such result is possible for maximum degree six or higher, even for planar graphs.

Paper reference: doi:10.1016/S0095-8956(02)00006-0

Date received: April 20, 2001