info prev up next book cdrom email home

Irredundant Ramsey Number

Let $G_1$, $G_2$, ..., $G_t$ be a $t$-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 Edges colored with the $i$th color. The irredundant Ramsey number $s(q_1, \ldots, q_t)$ is the smallest Integer $n$ such that for any $t$-Edge coloring of $K_n$, the Complement Graph $\overline {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

\begin{displaymath}
s(q_1, \ldots, q_t)\leq R(q_1, \ldots, q_t).
\end{displaymath}

For a summary, see Mynhardt (1992).

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


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.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26