Regresar

Some infinite families of Ramsey (P<inf>3</inf>, P<inf>n</inf>)-minimal trees

Abstract:

For any given two graphs G and H, the notation F → (G, H) means that for any red-blue coloring of all the edges of F will create either a red subgraph isomorphic to G or a blue subgraph isomorphic to H. A graph F is a Ramsey (G, H)- minimal graph if F →(G, H) but F - e → (G, H), for every e ∈ E(F). The class of all Ramsey (G, H)-minimal graphs is denoted by R(G, H). In this paper, we construct some infinite families of trees belonging to R(P3, Pn), for n = 8 and 9. In particular, we give an algorithm to obtain an infinite family of trees belonging to R(P3, Pn), for n ≥ 10.