51. ON TWO GRAPH PARTITIONING QUESTIONS
- Author
-
Yoomi Rho
- Subjects
Discrete mathematics ,Book embedding ,Dense graph ,General Mathematics ,Complete bipartite graph ,Planar graph ,law.invention ,Combinatorics ,symbols.namesake ,Pathwidth ,law ,Outerplanar graph ,Line graph ,symbols ,Forbidden graph characterization ,Mathematics - Abstract
M. Junger, 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.
- Published
- 2005