
The Library
A new bound for the 2/3 conjecture
Tools
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.
|
Text
WRAP_Kral_kls%2B12.pdf - Accepted Version Download (397Kb) | Preview |
Official URL: http://dx.doi.org/10.1017/S0963548312000612
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: |
|
||||
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
Downloads per month over past year