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
    0 references
    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

    Identifiers