TOPICS
Search

Irredundant Ramsey Number


Let G_1, G_2, ..., G_t be a t-graph edge coloring of the complete graph K_n, where for each i=1, 2, ..., t, G_i is the spanning subgraph of K_n consisting of all graph edges colored with the ith color. The irredundant Ramsey number s(q_1,...,q_t) is the smallest integer n such that for any t-graph edge coloring of K_n, the graph complement G_i^_ has an irredundant set of size q_i for at least one i=1, ..., t. Irredundant Ramsey numbers were introduced by Brewster et al. (1989) and satisfy

 s(q_1,...,q_t)<=R(q_1,...,q_t).

For a summary, see Mynhardt (1992).

sboundsreference
s(3,3)6Brewster et al. 1989
s(3,4)8Brewster et al. 1989
s(3,5)12Brewster et al. 1989
s(3,6)15Brewster et al. 1990
s(3,7)18Chen and Rousseau 1995, Cockayne et al. 1991
s(4,4)13Cockayne et al. 1992
s(3,3,3)13Cockayne and Mynhardt 1994

Explore with Wolfram|Alpha

References

Brewster, R. C.; Cockayne, E. J.; and Mynhardt, C. M. "Irredundant Ramsey Numbers for Graphs." J. Graph Theory 13, 283-290, 1989.Brewster, R. C.; Cockayne, E. J.; and Mynhardt, C. M. "The Irredundant Ramsey Number s(3,6)." Quaest. Math. 13, 141-157, 1990.Chen, G. and Rousseau, C. C. "The Irredundant Ramsey Number s(3,7)." J. Graph. Th. 19, 263-270, 1995.Cockayne, E. J.; Exoo, G.; Hattingh, J. H.; and Mynhardt, C. M. "The Irredundant Ramsey Number s(4,4)." Util. Math. 41, 119-128, 1992.Cockayne, E. J.; Hattingh, J. H.; and Mynhardt, C. M. "The Irredundant Ramsey Number s(3,7)." Util. Math. 39, 145-160, 1991.Cockayne, E. J. and Mynhardt, C. M. "The Irredundant Ramsey Number s(3,3,3)=13." J. Graph Th. 18, 595-604, 1994.Hattingh, J. H. "On Irredundant Ramsey Numbers for Graphs." J. Graph Th. 14, 437-441, 1990.Mynhardt, C. M. "Irredundant Ramsey Numbers for Graphs: A Survey." Congres. Numer. 86, 65-79, 1992.

Referenced on Wolfram|Alpha

Irredundant Ramsey Number

Cite this as:

Weisstein, Eric W. "Irredundant Ramsey Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/IrredundantRamseyNumber.html

Subject classifications