Minimal vertex Ramsey graphs and minimal forbidden subgraphs Original Research Article

Let P be a property of graphs. A graph G is vertex (P,k)-colourable if the vertex set V(G) of G can be partitioned into k sets V1, V2,…,Vk such that the subgraph G[Vi] of G belongs to P, i=1,2,…,k. If P is a hereditary property, then the set of minimal forbidden subgraphs of P is defined as follows: F(P)={G: G∉P but each proper subgraph H of G belongs to P}. In this paper we investigate the property On: each component of G has at most n+1 vertices. We construct minimal forbidden subgraphs for the property (Onk) “to be (On,k)-colourable”. We write G→v (H)k, k⩾2, if for each k-colouring V1,V2,…,Vk of a graph G there exists i, 1⩽i⩽k, such that the graph induced by the set Vi contains H as a subgraph. A graph G is called (H)k-vertex Ramsey minimal if G→v (H)k, but G′↛v (H)k for any proper subgraph G′ of G. The class of (P3)k-vertex Ramsey minimal graphs is investigated.