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

• Autorzy: Shinya Fujita
• Języki publikacji: EN

Abstrakty

EN

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_{1,t}$-free, then min{Δ(G),Δ(G̅)} ≤ r(t- 1,t)-1 where r(t-1,t) is the Ramsey number.

Słowa kluczowe

EN

claw-free; complement; maximum degree

Kategorie tematyczne

• 05C75: Structural characterization of families of graphs
• 05C99: None of the above, but in this section

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2005
• Tom: 25
• Numer: 3
• Strony: 267-272

Daty

wydano

2005

otrzymano

2003-11-23

poprawiono

2004-11-06

Twórcy

autor

Shinya Fujita

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

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1280