solidot新版网站常见问题,请点击这里查看。

A natural generalisation in graph Ramsey theory. (arXiv:1708.07060v2 [math.CO] UPDATED)

来源于:arXiv
In this note we study graphs $G_r$ with the property that every colouring of $E(G_r)$ with $r+1$ colours admits a copy of some graph $H$ using at most $r$ colours. Such graphs occur naturally at intermediate steps in the synthesis of a $2$-colour Ramsey graph $G_1\longrightarrow H$. For $H=K_n$ we prove a result on building a $G_{r}$ from a $G_{r+1}$ and establish Ramsey-infiniteness. From the structural point of view, we characterise the class of the minimal $G_r$ in the case when $H$ is relaxed to be the graph property of containing a cycle; we then use it to progress towards a constructive description of that class by proving both a reduction and an extension theorem. 查看全文>>