Record Details

Plane triangulations are 6-partitionable

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Plane triangulations are 6-partitionable
 
Creator DIWAN, AJIT A
KURHEKAR, MANISH P
 
Subject graph
plane
triangulation
partition
 
Description Given a graph G=(V,E) and k positive integers n1,n2,...,nk such that ∑i=1k ni=|V|, we wish to find a partition P1,P2,...,Pk of the vertex set V such that |Pi|= ni and Pi induces a connected subgraph of G for all i, 1⩽i⩽k. Such a partition is called a k-partition of G. A graph G with n vertices is said to be k-partitionable if there exists a k-partition of G for any partition of n into k parts. Lovász (Acta Math. Acad. Sci. Hungar. 30 (1977) 241) showed that k-connected graphs are k-partitionable. In this paper we prove that plane triangulations are 6-partitionable. This result is the best possible as there exist plane triangulations which are not 7-partitionable.
 
Publisher Elsevier
 
Date 2009-05-08T02:33:56Z
2011-12-08T06:54:02Z
2011-12-26T13:01:51Z
2011-12-27T05:47:20Z
2009-05-08T02:33:56Z
2011-12-08T06:54:02Z
2011-12-26T13:01:51Z
2011-12-27T05:47:20Z
2002
 
Type Article
 
Identifier Discrete Mathematics 256(1-2), 91-103
0012-365X
10.1016/S0012-365X(01)00463-0
http://hdl.handle.net/10054/1296
http://dspace.library.iitb.ac.in/xmlui/handle/10054/1296
 
Language en