Type: Article

Size Ramsey numbers of stars versus cliques

Journal: Journal of Graph Theory (03649024)Year: 1 November 2019Volume: 92Issue: Pages: 275 - 286

Miralaei M.Omidi G.R.Shahsiah M.^a

a :University of Isfahan - IRAN(IR) - Isfahan

GreenDOI:10.1002/jgt.22453Language: English

Abstract

The size Ramsey number (Formula presented.) of two graphs (Formula presented.) and (Formula presented.) is the smallest integer (Formula presented.) such that there exists a graph (Formula presented.) on (Formula presented.) edges with the property that every red-blue colouring of the edges of (Formula presented.) yields a red copy of (Formula presented.) or a blue copy of (Formula presented.). In 1981, Erdős observed that (Formula presented.) and he conjectured that this upper bound on (Formula presented.) is sharp. In 1983, Faudree and Sheehan extended this conjecture as follows: (Formula presented.) They proved the case (Formula presented.). In 2001, Pikhurko showed that this conjecture is not true for (Formula presented.) and (Formula presented.), by disproving the mentioned conjecture of Erdős. Here, we prove Faudree and Sheehan's conjecture for a given (Formula presented.) and (Formula presented.). © 2019 Wiley Periodicals, Inc.