Claw‐free circular‐perfect graphs |
| |
| Authors: | Arnaud Pêcher Xuding Zhu |
| |
| Institution: | 1. University of Bordeaux 1 (Labri, Inria), 351 Cours de la Libération, 33405 Talence, France;2. Department of Applied Mathematics, National Sun Yat‐Sen University, Kaohsiung, Taiwan;3. National Center for Theoretical Sciences, Taiwan |
| |
| Abstract: | The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that if G is a connected claw‐free circular‐perfect graph with χ(G)>ω(G), then min{α(G), ω(G)}=2. We use this result to design a polynomial time algorithm that computes the circular chromatic number of claw‐free circular‐perfect graphs. A consequence of the strong perfect graph theorem is that minimal imperfect graphs G have min{α(G), ω(G)}=2. In contrast to this result, it is shown in Z. Pan and X. Zhu European J Combin 29(4) (2008), 1055–1063] that minimal circular‐imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. In this article, we prove that claw‐free minimal circular‐imperfect graphs G have min{α(G), ω(G)}≤3. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 163–172, 2010 |
| |
| Keywords: | circular‐perfect graph claw‐free graph |
|
|
