The strong perfect-graph conjecture is true for K_1,3-free graphs

Abstract

The partition number θ of a graph G is the minimum number of cliques which cover the points of G. The independence number α of G is the maximum number of points in an independent (stable) set of G. A graph G is said to be perfect if θ(H)=α(H) for every induced subgraph H of G. Berge's strong perfect-graph conjecture states that G is perfect iff G does not contain C_2n+1 and _2n+1, n≥2 as an induced subgraph. In this paper we show that this conjecture is true for graphs which do not have K_{1, 3} as an induced subgraph. The line graphs thus belong to the class of graphs for which the conjecture is true.