{"id":"arxiv/2605.22077","url":"https://arxiv.org/abs/2605.22077","tags":["math.CO"],"score":0,"title":"Induced/Incomparable versus Ramsey","domain":"math.CO","source":"arxiv","authors":["Yair Caro","Zsolt Tuza","Christina Zarb"],"reviews":0,"subject":"math.CO","summary":"We consider the following problem: Let $H$ and $F$ be two graphs on $k$ vertices and assume $F \\neq H$. We say that $H$ and $F$ are incomparable if neither $F$ nor $H$ contains the other. Let $H$ be a graph on $k$ vertices and let $G$ be a graph on at least $k$ vertices. Then $G$ is said to be $H$-exact if any induced subgraph of $G$ on $k$ vertices is either isomorphic to $H$ or incomparable with $H$. Exact($H$) is the family of all graphs $G$ which are $H$-exact. We pose the following problem: For a graph $H$ on $k$ vertices, determine or estimate $f(H) = \\max \\{n: \\exists G \\in…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-21","reactions":{}}