Avoidance colourings for small nonclassical Ramsey numbers
Alewyn P Burger, Jan H van Vuuren
Abstract
The irredundant Ramsey number s=s(m,n)
[upper
domination Ramsey number u=u(m,n),
respectively] is
the smallest natural number s [u,
respectively] such
that in any red-blue edge colouring (R,B) of the complete
graph
of order s [u, respectively], it holds that
IR(B)≥m
or IR(R)≥n [Γ(B)≥m or
Γ(R)≥n,
respectively], where Γ and IR denote
respectively
the upper domination number and the irredundance number of a graph.
Furthermore,
the mixed irredundant Ramsey number t=t(m,n)
[mixed
domination Ramsey number v=v(m,n), respectively] is
the
smallest natural number t [v, respectively]
such
that in any red-blue edge colouring (R,B) of the complete
graph
of order t [v, respectively], it holds that
IR(B)≥m
or β(R)≥ n [Γ(B)≥m
or
β(R)≥n, respectively], where
β
denotes the independent domination number of a graph. These four
classes
of non-classical Ramsey numbers have previously been studied in the
literature.
In this paper we introduce a new Ramsey number w=w(m,n),
called
the irredundant-domination Ramsey number, which is the
smallest
natural number w such that in any red-blue edge colouring
(R,B)
of the complete graph of order w, it holds that
IR(B)≥m
or Γ(R)≥n. A computer search is employed to
determine
complete sets of avoidance colourings of small order for these five
classes
of nonclassical Ramsey numbers. In the process the fifteen previously
unknown
Ramsey numbers t(4,4)=14, t(6,3)=17,
u(4,4)=13,
v(4,3)=8, v(4,4)=14, v(5,3)=13,
v(6,3)=17,
w(3,3)=6, w(3,4)=w(4,3)=8,
w(4,4)=13,
w(3,5)=w(5,3)=12 and w(3,6)=w(6,3)=15 are
established.
Full Text: PDF PostScript