Path Ramsey Number for Random Graphs
Path Ramsey Number for Random Graphs
复制标题
DOI：
10.1017/s0963548315000279
复制
发表时间：
2014-05
期刊：
影响因子：
--
通讯作者：
Shoham Letzter
中科院分区：
文献类型：
--
作者：
Shoham Letzter
Answering a question raised by Dudek and Prałat, we show that if pn → ∞, w.h.p., whenever G = G(n, p) is 2-edge-coloured there is a monochromatic path of length (2/3 + o(1))n. This result is optimal in the sense that 2/3 cannot be replaced by a larger constant. As part of the proof we obtain the following result. Given a graph G on n vertices with at least $(1-\varepsilon)\binom{n}{2}$ edges, whenever G is 2-edge-coloured, there is a monochromatic path of length at least $(2/3 - 110\sqrt{\varepsilon})n$ . This is an extension of the classical result by Gerencsér and Gyárfás which says that whenever Kn is 2-coloured there is a monochromatic path of length at least 2n/3.
