Article in press
Authors:
Title:
Bounds for Irredundant and CO-Irredundant Ramsey Numbers
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2025-02-05 , Revised: 2025-08-14 , Accepted: 2025-08-22 , Available online: 2025-09-16 , https://doi.org/10.7151/dmgt.2604
Abstract:
A set of vertices $X\subseteq V$ in a simple graph $G(V,E)$ is irredundant
(CO-irredundant) if each vertex $x\in X$ is either isolated in the induced
subgraph $G[X]$ or else has a private neighbor $y\in V\setminus X$ ($y\in V$)
that is adjacent to $x$ and to no other vertex of $X$.
The irredundant Ramsey number $s(t_{1},\ldots,t_{l})$ and CO-irredundant Ramsey
number $s_{\operatorname{CO}}(t_{1},\ldots,t_{l})$ are respectively the minimum
$N$ such that every $l$-coloring of the edges of the complete graph $K_{N}$ on
$N$ vertices has a monochromatic irredundant set and a monochromatic
CO-irredundant set of size $t_{i}$ for some $1\leq i\leq l$.
In this paper, first, we establish a lower bound for the irredundant Ramsey
number $s(t_{1},\ldots,t_{l})$ using a random and probabilistic method, which
extends the lower bound for $s(t,t)$ due to Chen-Hattingh-Rousseau. Second,
using Krivelevich's lemma, we give an asymptotic lower bound for the
$\operatorname{CO}$-irredundant Ramsey number $s_{\operatorname{CO}}(m,n)$.
In the end, we improve the upper bound for $s(3,9)$ such that
$24\leq s(3,9)\leq 26$.
Keywords:
irredundant Ramsey number, $\operatorname{CO}$-irredundant Ramsey number, irredundant set
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer-Verlag, London, 2008).
https://doi.org/10.1007/978-1-84628-970-5 - R.C. Brewster, E.J. Cockayne and C.M. Mynhardt, Irredundant Ramsey numbers for graphs, J. Graph Theory 13 (1989) 283–290.
https://doi.org/10.1002/jgt.3190130303 - R.C. Brewster, E.J. Cockayne and C.M. Mynhardt, The irredundant Ramsey number $s(3,6)$, Quaest. Math. 13 (1990) 141–157.
https://doi.org/10.1080/16073606.1990.9631608 - A.P. Burger, J.H. Hattingh and J.H. van Vuuren, The mixed irredundant Ramsey numbers $t(3,7)=18$ and $t(3,8)=22$, Quaest. Math. 37 (2014) 571–589.
https://doi.org/10.2989/16073606.2014.894691 - A. Burger and J. Vuuren, The irredundance-related Ramsey numbers $s(3,8) = 21$ and $w(3,8) = 21$, Util. Math. 120 (2017) 93–107.
https://doi.org/10.61091/um120-08 - G. Chen, J.H. Hattingh and C.C. Rousseau, Asymptotic bounds for irredundant and mixed Ramsey numbers, J. Graph Theory 17 (1993) 193–206.
https://doi.org/10.1002/jgt.3190170208 - G. Chen and C.C. Rousseau, The irredundant Ramsey number $s(3,7)$, J. Graph Theory 19 (1995) 263–270.
https://doi.org/10.1002/jgt.3190190211 - E.J. Cockayne, G. Exoo, J.H. Hattingh and C.M. Mynhardt, The irredundant Ramsey number $s(4,4)$, Util. Math. 41 (1992) 119–128.
- E.J. Cockayne, J.H. Hattingh, J. Kok and C.M. Mynhardt, Mixed Ramsey numbers and irredundant Turán numbers for graphs, Ars Combin. 29 (1990) 57–68.
- E.J. Cockayne, S.T. Hedetniemi and D.J. Miller, Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull. 21 (1978) 461–468.
https://doi.org/10.4153/CMB-1978-079-5 - E.J. Cockayne, G. MacGillivray and J. Simmons, CO-irredundant Ramsey numbers for graphs, J. Graph Theory 34 (2000) 258–268.
https://doi.org/10.1002/1097-0118(200008)34:4<258::AID-JGT2>3.0.CO;2-4 - P. Erdős, On the number of complete subgraphs contained in certain graphs, Publ. Inst. Hungar. Acad. Sci. 7 (1962) 459–464.
- P. Erdős and J.H. Hattingh, Asymptotic bounds for irredundant Ramsey numbers, Quaest. Math. 16 (1993) 319–331.
https://doi.org/10.1080/16073606.1993.9631740 - A.M. Farley and N. Schacham, Senders in broadcast networks: open irredundancy in graphs, Congr. Numer. 38 (1983) 47–57.
- J.H. Hattingh, On irredundant Ramsey numbers for graphs, J. Graph Theory 14 (1990) 437–441.
https://doi.org/10.1002/jgt.3190140407 - M.A. Henningh and O.R. Oellermann, On upper domination Ramsey numbers of graphs, Discrete Math. 274 (2004) 125–135.
https://doi.org/10.1016/S0012-365X(03)00084-0 - M. Krivelevich, A lower bound for irredundant Ramsey numbers, Discrete Math. 183 (1998) 185–192.
https://doi.org/10.1016/S0012-365X(97)00055-1 - C.M. Mynhardt and A. Roux, Irredundance, in: Structures of Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Ed(s)), Dev. Math. 66, (Springer, Cham, 2021) 135–181.
https://doi.org/10.1007/978-3-030-58892-2_6 - V. Nikiforov, On the minimum number of $k$-cliques in graphs with restricted independence number, Combin. Probab. Comput. 10 (2001) 361–366.
https://doi.org/10.1017/S0963548301004722 - C.C. Rousseau and S.E. Speed, Mixed Ramsey numbers revisited, Combin. Probab. Comput. 12 (2003) 653–660.
https://doi.org/10.1017/S0963548303005704 - J.B. Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983) 83–87.
https://doi.org/10.1016/0012-365X(83)90273-X - J. Spencer, Asymptotic lower bounds for Ramsey functions, Discrete Math. 20 (1977) 69–76.
https://doi.org/10.1016/0012-365X(77)90044-9 - W. Sawin, An improved lower bound for multicolor Ramsey numbers and a problem of Erdős, J. Combin. Theory Ser. A 188 (2022) 105579.
https://doi.org/10.1016/j.jcta.2021.105579
Close