A new bound for the 2/3 conjecture

Daniel Král'; Chun Hung Liu; Jean Sébastien Sereni; Peter Whalen; Zelealem B. Yilma

doi:10.1017/S0963548312000612

A new bound for the 2/3 conjecture

Daniel Král', Chun Hung Liu, Jean Sébastien Sereni, Peter Whalen, Zelealem B. Yilma

Mathematics

Research output: Contribution to journal › Article › peer-review

16 Scopus citations

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.

Original language	English (US)
Pages (from-to)	384-393
Number of pages	10
Journal	Combinatorics Probability and Computing
Volume	22
Issue number	3
DOIs	https://doi.org/10.1017/S0963548312000612
State	Published - May 2013

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1017/S0963548312000612

Cite this

@article{82a599b132844af79e0839d43f629651,

title = "A new bound for the 2/3 conjecture",

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{\AA}'s, Faudree, Gould, Gy{\'a}rf{\'a}s, Rousseau and Schelp in 1989, is 22. It is conjectured that three vertices suffice.",

author = "Daniel Kr{\'a}l' and Liu, {Chun Hung} and Sereni, {Jean S{\'e}bastien} and Peter Whalen and Yilma, {Zelealem B.}",

year = "2013",

month = may,

doi = "10.1017/S0963548312000612",

language = "English (US)",

volume = "22",

pages = "384--393",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "3",

}

TY - JOUR

T1 - A new bound for the 2/3 conjecture

AU - Král', Daniel

AU - Liu, Chun Hung

AU - Sereni, Jean Sébastien

AU - Whalen, Peter

AU - Yilma, Zelealem B.

PY - 2013/5

Y1 - 2013/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84879924294&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84879924294&partnerID=8YFLogxK

U2 - 10.1017/S0963548312000612

DO - 10.1017/S0963548312000612

M3 - Article

AN - SCOPUS:84879924294

SN - 0963-5483

VL - 22

SP - 384

EP - 393

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 3

ER -

A new bound for the 2/3 conjecture

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this