## $$k$$-Ramsey classes and dimensions of graphs.(English)Zbl 0842.05063

A graph class $$\mathcal A$$ is $$k$$-Ramsey if for each element $$G\in {\mathcal A}$$ and each $$m\in N$$ there is an $$H\in {\mathcal A}$$ such that in each $$m$$-coloring of $$H$$ there is an induced subgraph isomorphic to $$G$$ that is colored with at most $$k$$ colors. The intersection dimension of a graph $$G$$ with respect to a class $$\mathcal A$$ of graphs is the number of graphs from $$\mathcal A$$ that one has to intersect to get a graph isomorphic to $$G$$ (if it exists). The intersection dimension of a class $$\mathcal A$$ of graphs relative to a class $$\mathcal B$$ of graphs is the supremum of the dimension of the elements of $$\mathcal A$$ with respect to $$\mathcal B$$. The author now proves the following theorem: If $$\mathcal A$$, $$\mathcal B$$ are two classes of graphs such that $$\mathcal A$$ is closed under induced subgraphs and the class $$\overline{\mathcal B}$$ of the complements of the graphs in $$\mathcal B$$ is $$k$$-Ramsey, then the intersection dimension of $$\mathcal A$$ relative to $$\mathcal B$$ is either infinite or bounded by $$k$$. He applies this theorem to various classes of graphs.

### MSC:

 05C55 Generalized Ramsey theory 05D10 Ramsey theory
Full Text: