×

All unicyclic Ramsey \((mK_2, P_4)\)-minimal graphs. (English) Zbl 1490.05175

Summary: For graphs \(F\), \(G\) and \(H\), we write \(F\rightarrow (G,H)\) to mean that if the edges of \(F\) are colored with two colors, say red and blue, then the red subgraph contains a copy of \(G\) or the blue subgraph contains a copy of \(H\). The graph \(F\) is called a Ramsey \((G,H)\) graph if \(F\rightarrow (G,H)\). Furthermore, the graph \(F\) is called a Ramsey \((G,H)\)-minimal graph if \(F\rightarrow(G,H)\) but \(F-e\not\rightarrow (G,H)\) for any edge \(e\in E(F)\). In this paper, we characterize all unicyclic Ramsey \((G,H)\)-minimal graphs when \(G\) is a matching \(mK_2\) for any integer \(m\geq 2\) and \(H\) is a path on four vertices.

MSC:

05C55 Generalized Ramsey theory
05D10 Ramsey theory

References:

[1] E. T. Baskoro and K. Wijaya, On Ramsey (2K2, K4)-minimal graphs,Mathematics in the 21st Century, Springer Proc. Math. Stat.98(2015), 11-17. · Zbl 1328.05114
[2] E. T. Baskoro and L. Yulianti, On Ramsey minimal graphs for 2K2versusPn, Adv. Appl. Discrete Math.8(2) (2011), 83-90. · Zbl 1239.05120
[3] S. A. Burr, P. Erd˝os, R. J. Faudree and R. H. Schelp, A class of Ramsey-finite graphs,Proc. Ninth Southeastern Conf. on Combin., Graph Theory and Computing, Boca Raton(1978), 171-180. · Zbl 0432.05038
[4] S. A. Burr, P. Erd˝os, R. J. Faudree, C. C. Rousseau and R. H. Schelp, Ramsey minimal graphs for matchings,The Theory and Applications of Graphs, Kalamazoo, Mich. (1980), 159-168. (Wiley, New York, 1981). · Zbl 0469.05048
[5] S. A. Burr, P. Erd˝os, R. Faudree, C. C. Rousseau and R. H. Schelp, Ramsey minimal graphs for forests,Discrete Math.38(10) (1982), 23-32. · Zbl 0489.05039
[6] R. Faudree, Ramsey minimal graphs for forests,Ars Combin.31(1991), 117- 124. · Zbl 0747.05062
[7] T. Luczak, On Ramsey minimal graphs,Electron. J. Combin.1(1994), #R4. E.T. BASKORO ET AL. / AUSTRALAS. J. COMBIN. 82 (3) (2022), 237-255255
[8] I. Mengersen and J. Oeckermann, Matching-star Ramsey sets,Discrete Appl. Math.95(1999), 417-424. · Zbl 0932.05063
[9] H. Muhshi and E. T. Baskoro, On Ramsey (3K2, P3)-minimal graphs,AIP Conf. Proc.1450(2012), 110-117. · Zbl 1433.05219
[10] S. P. Radziszowski, Small Ramsey numbers,Electron. J. Combin.(2017), DS1.15. · Zbl 0953.05048
[11] K. Wijaya, E. T. Baskoro, H. Assiyatun and D. Suprijanto, On unicyclic Ramsey (mK2, P3)-minimal graphs,Procedia Comp. Sci.74(2015), 10-14.
[12] K. Wijaya, E. T. Baskoro, H. Assiyatun and D. Suprijanto, On Ramsey (mK2, H)-minimal graphs,Graphs Combin.33(1) (2017), 233-243. · Zbl 1407.05239
[13] K. Wijaya, E. T. Baskoro, H. Assiyatun and D. Suprijanto, On Ramsey (4K2, P3)-minimal graphs,AKCE Int. J. Graphs Combin.15(2) (2018), 174- 186 · Zbl 1403.05070
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.