Ramsey minimal graphs for \(2K_2\) versus \(P_n\) (Q2885008)

Let \(G\) and \(H\) be a pair of graphs. A graph \(F\) is Ramsey for \((G,H)\) if every red-blue coloring of \(F\) contains a red \(G\) or a blue \(H\). A graph is Ramsey minimal for \((G,H)\), if it is Ramsey, but no proper subgraph is. Let \(\mathcal{R}(G,H)\) be the family of all Ramsey minimal graphs for \((G,H)\). \textit{S.A. Burr}, \textit{P. Erdős}, \textit{R.J. Faudree} and \textit{R.H. Schelp} [``A class of Ramsey-finite graphs,'' Proc. 9th southeast. Conf. on Combinatorics, graph theory, and computing, Boca Raton 1978, 171--180 (1978; Zbl 0432.05038)] proved that for every natural number \(m\) and every graph \(H\) the family \(\mathcal{R}(mK_2,H)\) is finite. This paper studies \(\mathcal{R}(2K_2,P_n)\) for \(n\geq 3\) in more detail. NEWLINENEWLINENEWLINE NEWLINEIt is shown that \(2P_n\) is the only disconnected graph in \(\mathcal{R}(2K_2,P_n)\), and that \(\mathcal{R}(2K_2,P_n)\) contains no tree. For \(n=4\) it is shown that \(\mathcal{R}(2K_2,P_4)=\{2P_4,C_7,C_6,C_5,C_4^+\}\), where \(C_4^+\) is the six-vertex graph obtained from \(C_4\) by adding pendant edges to a pair of adjacent vertices. A similar list is given for \(n=5\).