Chromatic number is Ramsey distinguishing
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:GAPL3D5Brecord.jsonopen to challenge →
read the original abstract
A graph $G$ is Ramsey for a graph $H$ if every colouring of the edges of $G$ in two colours contains a monochromatic copy of $H$. Two graphs $H_1$ and $H_2$ are Ramsey equivalent if any graph $G$ is Ramsey for $H_1$ if and only if it is Ramsey for $H_2$. A graph parameter $s$ is Ramsey distinguishing if $s(H_1)\neq s(H_2)$ implies that $H_1$ and $H_2$ are not Ramsey equivalent. In this paper we show that the chromatic number is a Ramsey distinguishing parameter. We also extend this to the multi-colour case and use a similar idea to find another graph parameter which is Ramsey distinguishing.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.