Subgraph counting identities and Ramsey numbers (Q1354725)

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\).