Small graphs on Ramsey minimal P4 versus P6

• Published in: AIP conference proceedings 2022-11, Vol.2639 (1)
• Main Authors: Rahmadani, Desi, Wahyuningsih, Sapti, Semanicova-Fenovcikova, Andrea, Cahyani, Denis Eka
• Format: Article
• Language: English
• Subjects: Graph theory; Graphs
• ISSN: 0094-243X; 1551-7616
• DOI: 10.1063/5.0109981

We consider two simple graphs G and H, the notation F → (G, H) means that for any red- blue coloring of all the edges of graph F contains either a red copy isomorphic to G or a blue copy isomorphic to H. A graph F is Ramsey (G, H)-minimal graph if F → (G, H) and for any edge e in F then F - e → (G, H). The set of all Ramsey minimal graphs for pair (G, H) is denoted by R(G, H). The Ramsey set for pair (G, H) is said to be Ramsey-finite or Ramsey-infinite if R(G, H) is finite or infinite, respectively. Several articles have discussed the problem of determining whether R(G, H) is finite (infinite). It is known that the set R(Pm, Pn), for 3 ≤ m ≤ n is Ramsey-infinite. Some partial results in R(P4, Pn), for n = 4 and n = 5 , have been obtained. Motivated by this, we are interested in determining graphs in R(P4, P6). In this paper, we determine some graphs of certain order in R(P4, P6).