On the Structure of Bull-Free Perfect Graphs, 2: the Weakly Chordal Case |
| |
Authors: | Celina MH De Figueiredo Frédéric Maffray Oscar Porto |
| |
Institution: | Universidade Federal do Rio de Janeiro, Instituto de Matemática, Caixa Postal 68530, 21944 Rio de Janeiro, RJ, Brasil. e-mail: celina@cos.ufrj.br, BR CNRS, Laboratoire Leibniz, 46 avenue Félix Viallet, 38031 Grenoble Cedex, France?e-mail: frederic.maffray@imag.fr, FR PUC-Rio, Department de Engenharia Elétrica, Rua Marquês de S?o Vicente 225, Predio Cardeal Leme, Sala 401, CEP 22453, Rio de Janeiro, RJ, Brasil?e-mail: oscar@ele.puc-rio.br, BR
|
| |
Abstract: | A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. A graph is perfectly orderable if it
admits an ordering such that the greedy sequential method applied on this ordering produces an optimal coloring for every
induced subgraph. Chvátal conjectured that every bull-free graph with no odd hole or antihole is perfectly orderable. In a
previous paper we studied the structure of general bull-free perfect graphs, and reduced Chvátal's conjecture to the case
of weakly chordal graphs. Here we focus on weakly chordal graphs, and we reduce Chvátal's conjecture to a restricted case.
Our method lays out the structure of all bull-free weakly chordal graphs. These results have been used recently by Hayward
to establish Chvátal's conjecture for this restricted case and therefore in full.
Received: November 26, 1997?Final version received: February 27, 2001 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|