On the Choosability of Claw-Free Perfect Graphs |
| |
Authors: | Sylvain Gravier Frédéric Maffray Lucas Pastor |
| |
Affiliation: | 1.CNRS, Institut Fourier,University of Grenoble,Grenoble,France;2.CNRS, Laboratoire G-SCOP,University of Grenoble,Grenoble,France;3.Laboratoire G-SCOP,University of Grenoble,Grenoble,France |
| |
Abstract: | It has been conjectured that for every claw-free graph G the choice number of G is equal to its chromatic number. We focus on the special case of this conjecture where G is perfect. Claw-free perfect graphs can be decomposed via clique-cutset into two special classes called elementary graphs and peculiar graphs. Based on this decomposition we prove that the conjecture holds true for every claw-free perfect graph with maximum clique size at most 4. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|