Ramsey families which exclude a graph (Q1906854)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Ramsey families which exclude a graph
scientific article

    Statements

    Ramsey families which exclude a graph (English)
    0 references
    13 August 1996
    0 references
    For graphs \(A\) and \(B, A\to (B)^1_r\) means that for every \(r\)-coloring of the vertices of \(A\) there is a monochromatic copy of \(B\) in \(A\). A family \(\mathcal F\) of graphs is Ramsey if for each \(B\in {\mathcal F}\), there is a graph \(A\in {\mathcal F}\) such that \(A\to (B)^1_r\). \(\text{Forb}(G)\) is the family of graphs that contain no induced subgraph isomorphic to \(G\). It is known that if \(G\) is 2-connected, then \(\text{Forb}(G)\) is Ramsey. Let \(\mathcal K\) denote the family of connected graphs containing a cutvertex that is adjacent to all but precisely one vertex. It is shown that for many graphs \(G\in {\mathcal K}\), \(\text{Forb}(G)\) is not Ramsey; in fact, a specific conditon on \(G\) is given that implies that \(\text{Forb}(G)\) is not Ramsey. This settles the question about the existence of large classes of graphs that are not Ramsey.
    0 references
    Ramsey families
    0 references
    induced subgraph
    0 references
    0 references
    0 references
    0 references

    Identifiers