The reviewed record of science sign in
Pith

arxiv: 1909.02590 · v2 · pith:GAPL3D5B · submitted 2019-09-05 · math.CO

Chromatic number is Ramsey distinguishing

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:GAPL3D5Brecord.jsonopen to challenge →

classification math.CO
keywords ramseygraphdistinguishingparameterchromaticequivalentnumberanother
0
0 comments X
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.