Weakly triangulated graphs |
| |
Authors: | Ryan B Hayward |
| |
Institution: | School of Computer Science, McGill University, 805 Sherbrooke St. W., Montreal, Quebec H3A 2K6, Canada |
| |
Abstract: | A graph is triangulated if it has no chordless cycle with four or more vertices. It follows that the complement of a triangulated graph cannot contain a chordless cycle with five or more vertices. We introduce a class of graphs (namely, weakly triangulated graphs) which includes both triangulated graphs and complements of triangulated graphs (we define a graph as weakly triangulated if neither it nor its complement contains a chordless cycle with five or more vertices). Our main result is a structural theorem which leads to a proof that weakly triangulated graphs are perfect. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|