On the Ramsey numbers \(r(S_n, K_6-3K_2)\)
For every connected graph \(F\) with \(n\) vertices and every graph \(G\) with chromatic surplus \(s(G)\leq n\), the Ramsey number \(r(F,G)\) satisfies \( r(F,G) \geq (n-1)(\chi(G)-1) + s(G), \) where \(\chi(G)\) denotes the chromatic number of \(G\). If this lower bound is attained, then \(F\) is called \(G\)-good. For all connected graphs \(G\) with at most six vertices and \(\chi(G) \geq 4\), every tree \(T_n\) of order \(n\geq 5\) is \(G\)-good. In case of \(\chi(G) = 3\) and \(G \neq K_6-3K_2\), every non-star tree \(T_n\) is \(G\)-good except for some small \(n\), whereas \(r(S_n,G)\) for the star \(S_n = K_{1,n-1}\) in a few cases differs by at most 2 from the lower bound. In this note, we prove that the values of \(r(S_n,K_6-3K_2)\) are considerably larger for sufficiently large \(n\). Furthermore, exact values of \(r(S_n,K_6-3K_2)\) are obtained for small \(n\).
Authors
- Roland Lortz (ORCID: https://orcid.org/0000-0001-7009-4231)
- Ingrid Mengersen
Publication Details
- Journal
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Published
- 2025-03-16
- DOI
- https://doi.org/10.61091/jcmcc124-15
- Primary Topic
- Advanced Topology and Set Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00