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

Kratochvíl, Jan

Commentat. Math. Univ. Carol. 36, No. 2, 263-268 (1995).

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.

Reviewer: P.Braß (Greifswald)

MSC:

05C55	Generalized Ramsey theory
05D10	Ramsey theory

Keywords:

Ramsey classes; boxicity; interval graphs; split graphs; co-comparability graphs; intersection dimension