Asymptotic Bounds for CO-irredundant and Irredundant Ramsey Numbers

MaRDI QIDQ6504673arXivFDO

Authors Meng Ji, Yaping Mao, Ingo Schiermeyer

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Generalized Ramsey theory (05C55) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: A set of vertices $XsubseteqV$ in a simple graph $G(V,E)$ is irredundant if each vertex $xinX$ is either isolated in the induced subgraph $langleXangle$ or else has a private neighbor $yinVsetminusX$ that is adjacent to $x$ and to no other vertex of $X$. The emph{irredundant Ramsey number} $s(m,n)$ is the smallest $N$ such that in every red-blue coloring of the edges of the complete graph of order $N$, either the blue subgraph contains an $m$-element irredundant set or the red subgraph contains an $n$-element irredundant set. The emph{mixed Ramsey number} $t(m,n)$ is the smallest $N$ for which every red-blue coloring of the edges of $K_N$ yields an $m$-element irredundant set in the blue subgraph or an $n$-element independent set in the red subgraph. In this paper, we first improve the upper bound of $t(3,n)$; using this result, we confirm that a conjecture proposed by Chen, Hattingh, and Rousseau, that is, $li{m}_{nightarrowinfty}fract(m,n)r(m,n)=0$ for each fixed $mgeq3$, is true for $mleq4$. At last, we prove that $s(3,9)$ and $t(3,9)$ are both equal to $26$.

This page was built for publication: Asymptotic Bounds for CO-irredundant and Irredundant Ramsey Numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6504673)