Subgraph counting identities and Ramsey numbers
type: Item
instance of: scholarly article
title: Subgraph counting identities and Ramsey numbers
zbMATH Open document ID: 0869.05043
author: Brendan D. McKay
author: Stanisław P. Radziszowski
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-08-20T00:00:00Z
review text: For each vertex \(v\) of a graph \(G\), the number of subgraphs of each isomorphism class which lie in the neighbourhood or complementary neighbourhood of \(v\) is considered. These numbers, summed over \(v\), are shown to satisfy a series of identities. Using these, it is shown that \(R(5,5)\leq 49\) and \(R(4,6)\leq 41\), where \(R(m,n)\) is the usual Ramsey number. The authors also give some experimental evidence to support their conjecture that \(R(5,5)= 43\).
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 1006757
zbMATH Keywords: Ramsey number
reviewed by: Chris Jagger
describes a project that uses: Maple
describes a project that uses: LINDO
MaRDI profile type: Publication
OpenAlex ID: W2064794422
Wikidata QID: Q54278850
cites work: Q4002478
cites work: Q3912837
cites work: A lower bound for r(5, 5)
cites work: Q5577106
cites work: On Sets of Acquaintances and Strangers at any Party
cites work: Construction of Special Edge-Chromatic Graphs
cites work: Upper bounds for some Ramsey numbers
cites work: Q3663334
cites work: Q4017142
cites work: Linear programming in some Ramsey problems
cites work: R(4, 5) = 25
cites work: The value of the Ramsey numberr(3, 8)
cites work: Q4732489
cites work: On finite Ramsey numbers
cites work: Dichromatic graphs and Ramsey numbers
cites work: An upper bound for the Ramsey number M(5,4)
DOI: 10.1006/JCTB.1996.1741
description: scientific article; zbMATH DE number 1006757