Independence, clique size and maximum degree
type: Item
instance of: scholarly article
title: Independence, clique size and maximum degree
zbMATH Open document ID: 0576.05025
DOI: 10.1007/BF02579154
author: Siemion Fajtlowicz
published in: Combinatorica
publication date: 1984-01-01T00:00:00Z
review text: Given a graph G with n vertices, maximum degree p, clique size (q-1), and independence number \(\alpha\), the author has previously shown that \(\alpha /n\geq 2/(p+q)\) [Proc. 9th Southeast. Conf. Comb., Graph Theory, Comput., Boca Raton 1978, 269-274 (1978; Zbl 0434.05044)]. Furthermore, if equality holds, then 3q-2p\(\leq 5\); such graphs are called butterflies. Butterflies occur in Ramsey theory, as \textit{P. A. Catlin}'s counterexamples to the Hajós conjecture [J. Comb. Theory, Ser. B 26, 268-274 (1979; Zbl 0385.05033)] and in an article by \textit{B. Bollobás, S. Tucker} and the reviewer [Proc. 7th Southeast. Conf. Comb., Graph Theory, Comput., Baton Rouge 1976, 43-50 (1976; Zbl 0344.05156)]. Here the author proves that given natural numbers p and q with \(3q-2p=5\), there exists a unique butterfly with these parameters.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3920499
zbMATH Keywords: maximum degree
zbMATH Keywords: clique size
zbMATH Keywords: independence number
zbMATH Keywords: Butterflies
MaRDI profile type: Publication
cites work: Hajos' graph-coloring conjecture: Variations and counterexamples
cites work: On the conjecture of Hajos
cites work: Q3872499
description: scientific article; zbMATH DE number 3920499