Ramsey-Kuratowski numbers

Question

A simple graph is an ordered pair of sets $\,\Gamma:=(V\,E)\,$ such that $\,E\subseteq\binom V2.\ $ Kuratowski graph of the first kind is $\,K_n:=\left(V\,\,\binom V2\right),\,$ where $\,n:=|V|.\,$ And of the second type is

$$ K_{m\,n}\,:=\,(W\!\cup\!V\,\, \mu(W\times V)) $$

where $\,W\cap V=\emptyset,\,$ and $\,|W|=m\,$ and $\,|V|=n,\,$ and

$$\,\mu(W\times V)\,:=\,\{\{w\,v\}:\, (w\,v)\in W\times V\} $$

 

Q1 (single)  What is the least natural number $\,s\,$ such that for every edge red-green coloring of $\,K_s,\,$ graph $\,K_s\,$ contains a red subgraph isomorphic to $\,K_5\,$ or a green subgraph isomorphic to $\,K_{3\,3}\,$ ? Call this number $\,\mbox{RK}_{rg}.$

Q2 (double)  What is the least natural number $\,d\,$ such that for every edge red-green coloring of $\,K_d,\,$ graph $\,K_d\,$ contains a unicolored subgraph (totally red or totally green) isomorphic to $\,K_5\,$ or to $\,K_{3\,3}\,$ ? Call this number $\,\mbox{RK}_{xx}.$

Q3 (triple)  What is the least natural number $\,D\,$ such that every for every edge red-green coloring of $\,K_d,\,$ graph $\,K_d\,$ contains two unicolored subgraphs of the same color, one isomorphic to $\,K_5\,$ and the other one to $\,K_{3\,3}\,$ ? Call this number $\,\mbox{RK}_{YY}.$

REMARK   Of course, the above questions allude to Kuratowski's characterization of planar graphs (the theorem covered even more than graphs).

We have $$ \mbox{RK}_{xx}\,\le\,\mbox{RK}_{rg}\,\le\,\mbox{RK}_{YY} $$

and, let me quote Taras Banakh,

$$ RK_{xx}\le R(5,5)\le 48 $$

There is a conjecture that $\,\,R(5,5)=43.\,$ (end of quote).

Answer 1

Here are some bounds that I can extract from the dynamic survey Small Ramsey Numbers by Stanisław Radziszowski. Recall that for two graphs $G$ and $H$, $R(G,H)$ is the smallest integer $n$ such that every red-green edge colouring of $K_n$ contains a red $G$ subgraph or a green $H$ subgraph. In this notation, $\mathrm{RK}_{rg}=R(K_5, K_{3,3})$.

Claim. $13 \le \mathrm{RK}_{xx} \le 18.$

Proof. The lower bound $13 \le \mathrm{RK}_{xx}$ was proven by Will Brian in the above comments. For the upperbound, we have $\mathrm{RK}_{xx} \le R(K_{3,3}, K_{3,3}) = 18$. Note that $R(K_{3,3}, K_{3,3})=18$ was proven by H. Harborth and I. Mengersen in The Ramsey Number of $K_{3,3}$ (see Section 3.3.1 of the survey). $\Box$

Claim. $21 \le \mathrm{RK}_{rg} \le 47$.

Proof. For the lowerbound, observe that $K_{5,5,5,5}$ does not contain $K_5$ and the complement of $K_{5,5,5,5}$ does not contain $K_{3,3}$. For the upperbound, consider the edges incident to a fixed vertex. This gives the easy inductive bound $\mathrm{RK}_{rg} \le R(K_5, K_{2,3})+R(K_4, K_{3,3})+1$. Repeating the argument, we obtain $$\mathrm{RK}_{rg} \le R(K_5, K_{2,3}) + R(K_4, K_{2,3})+R(K_3, K_{3,3})+2.$$ In Section 5.9 of the survey, we have $R(B_3, K_4)=14$ and $R(B_3, K_5)=20$, where $B_3=K_2 + \overline{K_3}$. Since $K_{2,3} \subseteq B_3$, we have $R(K_5, K_{2,3}) \le 20$, and $R(K_4, K_{2,3}) \le 14$. Finally, in Section 3.2 of the survey, it is noted that $R(K_3, G)$ has been computed exactly for all connected graphs up to $9$ vertices. The value of $R(K_3, K_{3,3})$ is not given explicitly in the survey, but tracking down the references, we have $R(K_3, K_{3,3})=11$. Substituting, we obtain $\mathrm{RK}_{rg} \le 47$, as required. $\Box$

Finally, here is an upperbound for $\mathrm{RK}_{YY}$.

Claim. $\mathrm{RK}_{YY} \le 70$.

Proof. Since $K_6-e$ contains both $K_5$ and $K_{3,3}$, we have $$\mathrm{RK}_{YY} \le R(K_6-e, K_6-e) \le 70$$ (see Section 3.1 of the survey). $\Box$