A note on restricted vertex Ramsey numbers (Q1375624)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on restricted vertex Ramsey numbers |
scientific article |
Statements
A note on restricted vertex Ramsey numbers (English)
0 references
7 January 1998
0 references
We say \(G\rightarrow (a_1,\dots ,a_r)\) if for any \(r\)-colouring of the vertices of \(G\) there exists a copy of the complete graph \(K_{a_i}\) of colour \(i\) for some \(i=1,\dots ,r\). One would often like to find a graph \(G\) which fulfils this property yet ``locally'' is rather sparse. Thus, for \(2\leq a_1\leq\cdots\leq a_r<m\), let \(F(a_1,\dots ,a_r;m)=\min \{ |G|:K_m\not\subset G\) and \(G\rightarrow (a_1,\dots,a_r)\}\). In this note the value of \(F(a_1,\dots ,a_r;m)\) is computed for the first non-trivial case, when \(m=\sum_{i=1}^r(a_i-1)+1\).
0 references
Ramsey numbers
0 references
\(K_ r\)-free graphs
0 references
extremal graph theory
0 references