Loading...
Please wait, while we are loading the content...
Similar Documents
Partitioning into two graphs with only small components (1996).
| Content Provider | CiteSeerX |
|---|---|
| Author | Ding, Guoli Oporowski, Bogdan Sanders, Daniel P. Vertigan, Dirk |
| Abstract | . The paper presents several results on edge partitions and vertex partitions of graphs into 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 three has a vertex partition into two graphs, each of which has components on at most two vertices, and an edge partition into two graphs, each of which has components on at most eight vertices. It is not known whether similar results are true for maximum degree four and five, but we show that a similar result is false for maximum degree six or higher, even for planar graphs. 1. Introduction Graphs in this paper are simple, that is, without loops or multiple edges. The set of vertices of a graph G will be denoted by V (G), and the set of edges of G will be denoted by E(G). An edge partition of a graph G is a set fA 1 ; A 2 ; : : : ; A k g of subgraphs of G such that S k i=1 E(A i ) = E(G). Similarly, a ver... |
| File Format | |
| Publisher Date | 1996-01-01 |
| Access Restriction | Open |
| Subject Keyword | Edge Partition Small Component Vertex Partition Similar Result Planar Graph Multiple Edge Maximum Degree Admits Partition Set Fa Several Result Introduction Graph Bounded Size Component Arbitrary Graph |
| Content Type | Text |
| Resource Type | Article |
