ArticleOriginal scientific text

Title

On graphs G for which both g and G̅ are claw-free

Authors 1

Affiliations

  1. Department of Mathematics, Keio University, Hiyoshi, Kohoku-ku, Yokohama, 223-8522, Japan

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 K1,t-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

Bibliography

  1. H.J. Broersma, Z. Ryjacek and I. Schiermeyer, Closure concepts - a survey, Graphs and Combin. 16 (2000) 17-48, doi: 10.1007/s003730050002.
Pages:
267-272
Main language of publication
English
Received
2003-11-23
Accepted
2004-11-06
Published
2005
Exact and natural sciences