PDF

Discussiones Mathematicae Graph Theory 25(3) (2005) 267-272
DOI: https://doi.org/10.7151/dmgt.1280

ON GRAPHS G FOR WHICH BOTH G AND `G ARE CLAW-FREE

Shinya Fujita

Department of Mathematics
Keio University
Hiyoshi, Kohoku-ku, Yokohama, 223-8522, Japan
e-mail: shinyaa@comb.math.keio.ac.jp

Abstract

Let G be a graph with |V(G)| ≥ 10. We prove that if both G and `G are claw-free, then min{Δ(G), Δ(`G)} ≤ 2. As a generalization of this result in the case where | V(G)| is sufficiently large, we also prove that if both G and `G are K<sub>1,t</sub>-free, then min{Δ(G),Δ (`G)} ≤ r(t− 1,t)−1 where r(t−1,t) is the Ramsey number.

Keywords: claw-free, complement, maximum degree.

2000 Mathematics Subject Classification: 05C75, 05C99.

References

[1]	H.J. Broersma, Z. Ryjacek and I. Schiermeyer, Closure concepts - a survey, Graphs and Combin. 16 (2000) 17-48, doi: 10.1007/s003730050002.

Received 23 November 2003
Revised 6 November 2004