Bull-Free Weakly Chordal Perfectly Orderable Graphs |
| |
| Authors: | Ryan B Hayward |
| |
| Institution: | (1) Department of Computing Science, University of Alberta, Edmonton AB, T6G 2E1 Canada. e-mail: hayward@cs.ualberta.ca, CA |
| |
| Abstract: | Using doubly lexical orders and the notion of box partition due to de Figueiredo, Maffray, and Porto, we show that a certain
subclass of bull-free weakly chordal graphs is perfectly orderable. This together with results of de Figueiredo, Maffray,
and Porto confirms Chvátal's conjecture that bull-free graphs with no anti-hole and no odd hole are perfectly orderable; here
hole means induced cycle with five or more vertices.
Received: September 21, 1998?Final version received: January 23, 2001 |
| |
| Keywords: | , ,Bull-free graph, Weakly chordal graph, Perfectly orderable graph, Doubly lexical order, Box partition |
| 本文献已被 SpringerLink 等数据库收录！ |
|
