On 3-colorings of \(E(K_ n)\) (Q685557)

Let \(\alpha'(G)\) be the cardinality of a maximum matching (i.e. the edge independence number) and \(c(G)\) be the maximum order of the components of a graph \(G\). Suppose the edges of the complete graph \(K_ n\) are coloured with three colours 1, 2 and 3. Let \(G_ i\) be the subgraph of \(K_ n\) induced by the set of edges coloured with colour \(i\). For integers \(s \geq 1\) and \(k \geq 2\), let \(f(s,k)\) be the least integer \(n\) such that if the edges of \(K_ n\) are coloured with colours 1, 2 and 3, then either \(\alpha' (G_ 1) \geq s\) or \(\max \bigl\{ c(G_ 2),c(G_ 3) \bigr\} \geq k\). The author proves that \(f(s,k)= \max \{s+k-1,2s\}\). From this formula we know that \(f(s,k)\) is not a Ramsey number. According to the author, the problem of determining \(f(s,k)\) was raised by Bialostocki and was communicated to him by J. Kahn.