Optimizing weakly triangulated graphs

A graph is weakly triangulated if neither the graph nor its complement contains a chordless cycle with five or more vertices as an induced subgraph. We use a new characterization of weakly triangulated graphs to solve certain optimization problems for these graphs. Specifically, an algorithm which runs inO((n + e)n ³) time is presented which solves the maximum clique and minimum colouring problems for weakly triangulated graphs; performing the algorithm on the complement gives a solution to the maximum stable set and minimum clique covering problems. Also, anO((n + e)n ⁴) time algorithm is presented which solves the weighted versions of these problems.The author acknowledges the support of an N.S.E.R.C. Canada postgraduate scholarship.The author acknowledges the support of the U.S. Air Force Office of Scientific Research under grant number AFOSR 0271 to Rutgers University.