Chromatic Relatedness of Graphs

The \(F\)-free chromatic number \(\chi(M:-F)\) of a graph \(M\) is defined as the least number of classes in a partition of the vertices of \(M\) such that \(F\) does not occur as an induced subgraph in the subgraph induced by any of the colour classes. Two graphs \(G\) and \(H\) are called chromatically related if, for each positive integer \(k\), there exists a graph \(M\) such that \(\chi(M:-G) = \chi(M:-H) = k\), and distantly related whenever a chain of such relatednesses exists between them. Using a basic theorem of Folkman [3], we show that every two graphs on at least two vertices are distantly related.