The Library
A new bound for the 2/3 conjecture
Tools
Tools
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
|
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 > 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 | ||||
| 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
