Journal of the
Korean Mathematical Society
JKMS

ISSN(Print) 0304-9914 ISSN(Online) 2234-3008

Article

HOME ALL ARTICLES View

J. Korean Math. Soc. 2005; 42(4): 847-856

Printed July 1, 2005

Copyright © The Korean Mathematical Society.

On two graph partitioning questions

Yoomi Rho

Incheon University

Abstract

M. J\"{u}nger, G. Reinelt, and W. R. Pulleyblank asked the following questions ([2]). (1) Is it true that every simple planar $2$-edge connected bipartite graph has a $3$-partition in which each component consists of the edge set of a simple path? (2) Does every simple planar 2-edge connected graph have a $3$-partition in which every component consists of the edge set of simple paths and triangles? The purpose of this paper is to provide a positive answer to the second question for simple outerplanar $2$-vertex connected graphs and a positive answer to the first question for simple planar $2$-edge connected bipartite graphs one set of whose bipartition has at most $4$ vertices.

Keywords: planar graphs, outerplanar graphs, $2$-edge connected graphs, $2$-vertex connected graphs, bipartite graphs, $3$-partitions.

MSC numbers: Primary 05C70; Secondary 05C38, 05C40

Stats or Metrics

Share this article on :

Related articles in JKMS

more +