加载中…
Answering a question raised by Dudek and Pra\l{}at, we show that if , w.h.p.,~whenever is -coloured, there exists a monochromatic path of length . This result is optimal in the sense that cannot be replaced by a larger constant. As part of the proof we obtain the following result which may be of independent interest. We show that given a graph on vertices with at least edges, whenever is -edge-coloured, there is a monochromatic path of length at least . This is an extension of the classical result by Gerencs'er and Gy'arf'as which says that whenever is -coloured there is a monochromatic path of length at least .

生成讲解博客的中文版本

生成AI智能校验的中文版本