Abstract
In this paper we prove that if G is a connected claw-free graph with three pairwise non-adjacent vertices, with chromatic number χ and clique number ω, then χ≤2ω and the same for the complement of G. We also prove that the choice number of G is at most 2. ω, except possibly in the case when G can be obtained from a subgraph of the Schläfli graph by replicating vertices. Finally, we show that the constant 2 is best possible in all cases.
Original language | English (US) |
---|---|
Pages (from-to) | 560-572 |
Number of pages | 13 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 100 |
Issue number | 6 |
DOIs | |
State | Published - Nov 2010 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Keywords
- Choosability
- Claw-free graphs
- Colouring