A note on strong perfectness of graphs |
| |
Authors: | M. Preissmann D. de Werra |
| |
Affiliation: | (1) Département de Mathématiques Ecole Polytechnique Fédérale de Lausanne, Switzerland |
| |
Abstract: | In (strongly) perfect graphs, we define (strongly) canonical colorings; we show that for some classes of graphs, such colorings can be obtained by sequential coloring techniques. Chromatic properties ofP 4-free graphs based on such coloring techniques are mentioned and extensions to graphs containing no inducedP 5, orC 5 are presented. In particular we characterize the class of graphs in which any maximal (or minimal) nodex in the vicinal preorder has the following property: there is either noP 4 havingx as a midpoint or noP 4 havingx as an endpoint. For such graphs, according to a result of Chvatal, there is a simple sequential coloring algorithm. |
| |
Keywords: | Strongly Perfect Graphs Canonical Coloring Perfect Order Vicinal Preorder |
本文献已被 SpringerLink 等数据库收录! |