Access Restriction

Author Hsu, Wen-Lian
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1987
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract An $\textit{O}(\textit{n}3)$ algorithm for recognizing planar graphs that do not contain induced odd cycles of length greater than 3 (odd holes) is presented. A planar graph with this property satisfies the requirement that its maximum clique size equal the minimum number of colors required for the graph (graphs all of whose induced subgraphs satisfy the latter property are perfect as defined by Berge). The algorithm presented is based on decomposing these graphs into essentially two special classes of inseparable component graphs that are easy to recognize. They are (i) planar comparability graphs and (ii) planar line graphs of those planar bipartite graphs whose maximum degrees are no greater than 3. Composition schemes for generating planar perfect graphs from those basic components are also provided. This decomposition algorithm can also be adapted to solve the corresponding maximum independent set and minimum coloring problems. Finally, the path-parity problem on planar perfect graphs is considered.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1987-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 34
Issue Number 2
Page Count 34
Starting Page 255
Ending Page 288

Open content in new tab

   Open content in new tab
Source: ACM Digital Library