Alewyn Petrus Burger ; Jan H. Vuuren - Avoidance colourings for small nonclassical Ramsey numbers

dmtcs:559 - Discrete Mathematics & Theoretical Computer Science, July 14, 2011, Vol. 13 no. 2 - https://doi.org/10.46298/dmtcs.559
Avoidance colourings for small nonclassical Ramsey numbers

Authors: Alewyn Petrus Burger ; Jan H. Vuuren

    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) \textgreater= m or IR(R) \textgreater= n [Gamma (B) \textgreater= m or Gamma(R) \textgreater= n, respectively], where Gamma 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) \textgreater= m or beta(R) \textgreater= n [Gamma(B) \textgreater= m or beta(R) \textgreater= n, respectively], where beta 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) \textgreater= m or Gamma(R) \textgreater= 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.


    Volume: Vol. 13 no. 2
    Section: Graph and Algorithms
    Published on: July 14, 2011
    Accepted on: June 9, 2015
    Submitted on: April 1, 2010
    Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

    Share

    Consultation statistics

    This page has been seen 163 times.
    This article's PDF has been downloaded 159 times.