Edge Coloring Planar Graphs with Two Outerplanar Subgraphs

Files

TR Number

TR-91-34

Date

1991-12-01

Journal Title

Journal ISSN

Volume Title

Publisher

Department of Computer Science, Virginia Polytechnic Institute & State University

Abstract

The standard problem of edge coloring a graph with k colors is equivalent to partitioning the edge set of the graph into k matchings. Here edge coloring is generalized by replacing matchings with outerplanar graphs. We give a polynomial-time algorithm that edge colors any planar graph with two outerplanar subgraphs. Two is clearly minimal for the class of planar graphs.

Description

Keywords

Citation