. Proof, Claw?free graphs are BCD?free In Step 3 of the algorithm, instead of checking G for being BCD?free one has just to check G for being claw?free. ? References [1] L. Babel, On the P 4 ?structure of line graphs, 1998.

L. Babel, A. Brandstädt, and V. B. Le, Recognizing the P4-structure of bipartite graphs, Discrete Applied Mathematics, vol.93, issue.2-3, pp.93-177, 1999.
DOI : 10.1016/S0166-218X(99)00104-3

L. Babel and S. Olariu, On the p-connectedness of graphs ??? a survey, Discrete Applied Mathematics, vol.95, issue.1-3, pp.95-106, 1999.
DOI : 10.1016/S0166-218X(99)00062-1

A. Brandstädt and V. B. Le, Recognizing the P4-structure of block graphs, Discrete Applied Mathematics, vol.99, issue.1-3, pp.349-366, 2000.
DOI : 10.1016/S0166-218X(99)00145-6

A. Brandstädt and V. B. Le, Tree- and forest-perfect graphs, Discrete Applied Mathematics, vol.95, issue.1-3, pp.141-162, 1999.
DOI : 10.1016/S0166-218X(99)00071-2

A. Brandstädt and V. B. , Le, Split?perfect graphs, to appear in

A. Brandstädt, V. B. Le, and S. Olariu, Efficiently Recognizing the P 4 -Structure of Trees and of Bipartite Graphs Without Short Cycles, Graphs and Combinatorics, vol.16, issue.4, pp.381-387, 2000.
DOI : 10.1007/s003730070002

V. Chvátal and N. Sbihi, Recognizing claw-free perfect graphs, Journal of Combinatorial Theory, Series B, vol.44, issue.2, pp.154-176, 1988.
DOI : 10.1016/0095-8956(88)90085-8

G. Ding, Recognizing the P 4 ?structure of a tree, Graphs and Combinatorics, pp.323-328, 1994.

M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, 1980.

B. Jamison and S. , P-Components and the Homogeneous Decomposition of Graphs, SIAM Journal on Discrete Mathematics, vol.8, issue.3, pp.448-463, 1995.
DOI : 10.1137/S0895480191196812

V. B. Le, Bipartite?perfect graphs, to appear in, Discrete Applied Mathematics

B. Reed, A semi-strong Perfect Graph theorem, Journal of Combinatorial Theory, Series B, vol.43, issue.2, pp.223-240, 1987.
DOI : 10.1016/0095-8956(87)90022-0

S. Sorg, Die P 4 ?Struktur von Kantengraphen bipartiter Graphen, Diploma thesis, Mathematisches Institut der Universität zu Köln, 1997.