Skip to Main content Skip to Navigation
Journal articles

Avoidance colourings for small nonclassical Ramsey numbers

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) \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.
Document type :
Journal articles
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990505
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 3:39:44 PM
Last modification on : Thursday, September 7, 2017 - 1:03:36 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:23:41 PM

File

1514-6370-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00990505, version 1

Collections

Citation

Alewyn Petrus Burger, Jan H. Vuuren. Avoidance colourings for small nonclassical Ramsey numbers. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 2 (2), pp.81--96. ⟨hal-00990505⟩

Share

Metrics

Record views

143

Files downloads

709