Maximum clique deleted from Ramsey graphs of a graph and paths. (English) Zbl 1532.90099
Summary: For graphs \(F, G\) and \(H\), let \(F\rightarrow (G,H)\) signify that any red-blue edge coloring of \(F\) contains either a red \(G\) or a blue \(H\), hence the Ramsey number \(R(G, H)\) is the smallest \(r\) such that \(K_r \rightarrow (G,H)\). Define \(K_t\) as the surplus clique of \((G, H)\) if \(K_r \setminus K_t \rightarrow (G,H)\), where \(r=R(G,H)\). For any graph \(G\) with \(s(G)=1\), we shall show that the maximum order of surplus clique of \((G, P_n)\) is exactly \(\lceil \frac{n}{2}\rceil\) for large \(n\).
MSC:
| 90C27 | Combinatorial optimization |
References:
| [1] | Burr, SA, Ramsey numbers involving graphs with long suspended paths, J Lond Math Soc, 24, 3, 405-413 (1981) · Zbl 0474.05051 · doi:10.1112/jlms/s2-24.3.405 |
| [2] | Chvátal, V., Tree-complete graph Ramsey numbers, J Graph Theory, 1, 93 (1977) · Zbl 0351.05120 · doi:10.1002/jgt.3190010118 |
| [3] | Erdős, P.; Faudree, R.; Rousseau, C.; Schelp, R., Multipartite graph-sparse graph Ramsey numbers, Combinatorica, 5, 4, 311-318 (1985) · Zbl 0593.05050 · doi:10.1007/BF02579245 |
| [4] | Haghi, S.; Maimani, H.; Seify, A., Star-critical Ramsey numbers of \(F_n\) versus \(K_4\), Discrete Appl Math, 217, 2, 203-209 (2017) · Zbl 1358.05186 · doi:10.1016/j.dam.2016.09.012 |
| [5] | Hao, Y.; Lin, Q., Star-critical Ramsey numbers for large generalized fans and books, Discrete Math, 341, 12, 3385-3393 (2018) · Zbl 1397.05194 · doi:10.1016/j.disc.2018.08.025 |
| [6] | Hook, J., Critical graphs for \(R(P_n, P_m)\) and the star-critical Ramsey number for paths, Discuss Math Graph Theory, 35, 4, 689-701 (2015) · Zbl 1327.05228 · doi:10.7151/dmgt.1827 |
| [7] | Hook, J.; Isaak, G., Star-critical Ramsey numbers, Discrete Appl Math, 159, 5, 328-334 (2011) · Zbl 1207.05212 · doi:10.1016/j.dam.2010.11.007 |
| [8] | Jayawardene, C.; Narváez, D.; Radziszowski, S., Star-critical Ramsey numbers of cycles versus \(K_4\), Discuss Math Graph Theory, 41, 2, 381-390 (2021) · Zbl 1458.05163 · doi:10.7151/dmgt.2190 |
| [9] | Li, Z.; Li, Y., Some star-critical Ramsey numbers, Discrete Appl Math, 181, 301-305 (2015) · Zbl 1304.05100 · doi:10.1016/j.dam.2014.09.014 |
| [10] | Liu, Y.; Chen, Y., Star-critical Ramsey numbers of cycles versus wheels, Graphs Combin, 37, 6, 2167-2172 (2021) · Zbl 1479.05219 · doi:10.1007/s00373-021-02343-4 |
| [11] | Parsons, TD, Path-star Ramsey numbers, J Comb Theory Ser B, 17, 51-58 (1974) · Zbl 0282.05110 · doi:10.1016/0095-8956(74)90048-3 |
| [12] | Pei, C.; Li, Y., Ramsey numbers involving a long path, Discrete Math, 339, 2, 564-570 (2016) · Zbl 1327.05230 · doi:10.1016/j.disc.2015.09.033 |
| [13] | Pokrovskiy, A.; Sudakov, B., Ramsey goodness of paths, J Comb Theory Ser B, 122, 384-390 (2017) · Zbl 1350.05101 · doi:10.1016/j.jctb.2016.06.009 |
| [14] | Rousseau, C.; Sheehan, J., A class of Ramsey problems involving trees, J Lond Math Soc, 18, 3, 392-396 (1978) · Zbl 0393.05037 · doi:10.1112/jlms/s2-18.3.392 |
| [15] | Wang, Y.; Li, Y., Deleting edges from Ramsey graphs, Discrete Math, 343, 3, 111743 (2020) · Zbl 1431.05103 · doi:10.1016/j.disc.2019.111743 |
| [16] | Wang, Y.; Li, Y.; Li, Y., Star-critical Ramsey numbers involving graphs with long suspended paths, Discrete Math, 344, 3, 112233 (2021) · Zbl 1456.05116 · doi:10.1016/j.disc.2020.112233 |
| [17] | Wu, Y.; Sun, Y.; Radziszowski, S., Wheel and star-critical Ramsey numbers for quadrilateral, Discrete Appl Math, 186, 260-271 (2015) · Zbl 1311.05122 · doi:10.1016/j.dam.2015.01.003 |
| [18] | Zhang, Y.; Broersma, H.; Chen, Y., On star-critical and upper size Ramsey numbers, Discrete Appl Math, 202, 174-180 (2016) · Zbl 1330.05157 · doi:10.1016/j.dam.2015.08.020 |
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.
