Independence, clique size and maximum degree (Q1065018): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hajos' graph-coloring conjecture: Variations and counterexamples / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the conjecture of Hajos / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3872499 / rank | |||
Normal rank |
Latest revision as of 19:09, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Independence, clique size and maximum degree |
scientific article |
Statements
Independence, clique size and maximum degree (English)
0 references
1984
0 references
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.
0 references
maximum degree
0 references
clique size
0 references
independence number
0 references
Butterflies
0 references