The relationship between some nonclassical Ramsey numbers
| Autor: | Dzido, Tomasz, Zakrzewska, Renata |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The upper (mixed) domination Ramsey number $u(m, n)$($v(m,n)$) is the smallest integer $p$ such that every $2$-coloring of the edges of $K_p$ with color red and blue, $\Gamma(B) \geq m$ or $\Gamma(R) \geq n$ ($\beta(R) \geq n$); where $B$ and $R$ is the subgraph of $K_p$ induced by blue and red edges, respectively; $\Gamma(G)$ is the maximum cardinality of a minimal dominating set of a graph $G$. First, we prove that $v(3,n)=t(3,n)$ where $t(m,n)$ is the mixed irredundant Ramsey number i.e. the smallest integer $p$ such that in every two-coloring $(R, B)$ of the edges of $K_p$, $IR(B) \geq m$ or $\beta(R) \geq n$ ($IR(G)$ is the maximum cardinality of an irredundant set of $G$). To achieve this result we use a characterization of the upper domination perfect graphs in terms of forbidden induced subgraphs. By the equality we determine two previously unknown Ramsey numbers, namely $v(3,7)=18$ and $v(3,8) = 22$. In addition, we solve other four remaining open cases from Burger's {\it et. al.} article, which listed all nonclassical Ramsey numbers. We find that $u(3,7)=w(7,3)=18$, $u(3,8) = w(8,3) = 21$, where $w(m,n)$ is the irredundant-domination Ramsey number introduced by Burger and Van Vuuren in 2011. Comment: We found a mistake in the proof of the main theorem. May be the mistake can be corrected, but we can not do it for now. Unfortunately, the remaining theorems in the paper also use the same argument |
| Databáze: | arXiv |
| Externí odkaz: |
|