A multiplicative inequality for vertex Folkman numbers (Q941354): Difference between revisions

For a graph \(G\) and positive integers \(a_1,\dotsc,a_r\) the notation \(G \to (a_1,\dotsc,a_r)\) means that every vertex \(r\)-coloring of \(G\) contains a monochromatic clique on \(a_i\) vertices in color \(i\) for some \(i \in \{1,\dotsc,r\}\). The vertex Folkman number \(F(a_1,\dotsc,a_r;q)\) is the least number of vertices in a \(K_q\)-free graph \(G\) such that \(G \to (a_1,\dotsc,a_r)\). \textit{J. Folkman} [``Graphs with monochromatic complete subgraphs in every edge coloring'', SIAM J. Appl. Math. 18, 19--24 (1970; Zbl 0193.53103)] showed that \(F(a_1,\dotsc,a_r;q)\) is finite whenever \(q > \max(a_1,\dotsc,a_r)\). In this paper the bound \[ F(a_1b_1,\dotsc,a_rb_r;st+1) \leq F(a_1,\dotsc,a_r;s+1)F(b_1,\dotsc,b_r;t+1) \] is established. The main step is this: If \(A \to (a_1,\dotsc,a_r)\) and \(B \to (b_1,\dotsc,b_r)\), then \(A[B] \to (a_1b_1,\dotsc,a_r b_r)\), where \(A[B]\) denotes the graph composition of \(A\) and \(B\), i.e. the graph obtained from \(A\) by replacing each vertex of \(A\) with a copy of \(B\).