On the Ramsey Number for Cycle with Respect to Identical Copies of Complete Graphs

I Wayan Sudarsana1
1Combinatorial and Applied Mathematics Research Group (CAMRG), Department of Mathematics, Faculty of Mathematics and Natural Sciences, Tadulako University Jalan Soekarno-Hatta Km. 8, Palu 94117, Indonesia.

Abstract

For graphs \(G\) and \(H\), Ramsey number \(R(G, H)\) is the smallest natural number \(n\) such that no \((G, H)\)-free graph on \(n\) vertices exists. In 1981, Burr [5] proved the general lower bound \(R(G, H) \geq (n – 1)(\chi(H) – 1) + \sigma(H)\), where \(G\) is a connected graph of order \(n\), \(\chi(H)\) denotes the chromatic number of \(H\) and \(\sigma(H)\) is its chromatic surplus, namely, the minimum cardinality of a color class taken over all proper colorings of \(H\) with \(\chi(H)\) colors. A connected graph \(G\) of order \(n\) is called good with respect to \(H\), \(H\)-good, if \(R(G, H) = (n – 1)(\chi(H) – 1) + \sigma(H)\). The notation \(tK_m\) represents a graph with \(t\) identical copies of complete graph \(K_m\). In this note, we discuss the goodness of cycle \(C_n\) with respect to \(tK_m\) for \(m, t \geq 2\) and sufficiently large \(n\). Furthermore, it is also provided the Ramsey number \(R(G, tK_m)\), where \(G\) is a disjoint union of cycles.