Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657074 | Journal of Combinatorial Theory, Series B | 2010 | 13 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics