Induced/Incomparable versus Ramsey

Abstract

We consider the following problem: Let $H$ and $F$ be two graphs on $k$ vertices and assume $F\ne 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 \text{Exact}(H),|V(G)|=n\}$. Among the many results obtained in this paper the following are representatives concerning trees and matchings: 1. For a tree on $k\ge 3$ vertices, $(k-1)(\lceil \frac{k}{2}\rceil -1)\le f(T)\le (k-1{)}^2$. 2. For $k\ge 4$, $f(K_{1,k-1})=(k-1)(k-2)$. 3. For $k\ge 5$, $f(P_k)=\frac{(k-1{)}^2}{2}$ if $k$ is odd and $f(P_k)=\frac{(k-1)(k-2)}{2}+1$ if $k$ is even. 4. $f(n{K}_2)=3n$ for $n=2,3$ and $f(n{K}_2)=4n-4$ for $n\ge 4$.