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