### Recognizing planar perfect graphsRecognizing planar perfect graphs

Access Restriction
Subscribed

 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

Source: ACM Digital Library