Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6742
Title: Extending Planar Graph Algorithms to $K_{3}$,$_{3}$-free Graphs
Authors: Khuller, Samir
Keywords: computer science
technical report
Issue Date: Mar-1988
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-902
Abstract: For several problems, restricting attention to special classes of graphs has yielded better algorithms. In particular, restricting to planar graphs yields efficient parallel algorithms for several graph problems. In this paper we extend these algorithms to $K_{3}$,$_{3}$-free graphs, showing that the restriction of planarity is not important. The three problems dealt with are: graph coloring, depth first search and maximal independent sets. As a corollary we show that $K_{3}$,$_{3}$-free graphs are five colorable (this bound is tight).
URI: http://hdl.handle.net/1813/6742
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
88-902.pdf1.15 MBAdobe PDFView/Open
88-902.ps275.69 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us