\(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.


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