Král', Daniel, Liu, Chun-Hung, Sereni, Jean-Sébastien, Whalen, Peter and Yilma, Zelealem B. (2013) A new bound for the 2/3 conjecture. Combinatorics, Probability and Computing, Volume 22 (Number 3). pp. 384-393. doi:10.1017/S0963548312000612 ISSN 0963-5483.

Preview

Text WRAP_Kral_kls%2B12.pdf - Accepted Version Download (397Kb) | Preview

Request Changes to record.

Abstract

We show that any n-vertex complete graph with edges coloured with three colours contains a set of at most four vertices such that the number of the neighbours of these vertices in one of the colours is at least 2n/3. The previous best value, proved by Erdős, Faudree, Gould, Gyárfás, Rousseau and Schelp in 1989, is 22. It is conjectured that three vertices suffice.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Library of Congress Subject Headings (LCSH):	Complete graphs , Graph theory
Journal or Publication Title:	Combinatorics, Probability and Computing
Publisher:	Cambridge University Press
ISSN:	0963-5483
Official Date:	May 2013
Dates:	Date Event May 2013 Published
Volume:	Volume 22
Number:	Number 3
Page Range:	pp. 384-393
DOI:	10.1017/S0963548312000612
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Date of first compliant deposit:	25 December 2015
Date of first compliant Open Access:	25 December 2015
Funder:	European Research Council (ERC), Seventh Framework Programme (European Commission), Centre national de la recherche scientifique (France) (CNRS), France. Agence nationale de la recherche (ANR)
Grant number:	259385 (ERC) ; anr 10 jcjc 0204 01 (ANR)

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads