Edge Coloring Planar Graphs with Two Outerplanar Subgraphs

dc.contributor.authorHeath, Lenwood S.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:36:40Zen
dc.date.available2013-06-19T14:36:40Zen
dc.date.issued1991-12-01en
dc.description.abstractThe 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.en
dc.format.mimetypeapplication/pdfen
dc.identifierhttp://eprints.cs.vt.edu/archive/00000279/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000279/01/TR-91-34.pdfen
dc.identifier.trnumberTR-91-34en
dc.identifier.urihttp://hdl.handle.net/10919/19716en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.relation.ispartofHistorical Collection(Till Dec 2001)en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleEdge Coloring Planar Graphs with Two Outerplanar Subgraphsen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
TR-91-34.pdf
Size:
1.57 MB
Format:
Adobe Portable Document Format