# Ramsey-Kuratowski numbers

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 gree) 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).

• Observe that $RK_{xx}\le R(5,5)\le 48. The is a conjecture that R(5,5)=43. – Taras Banakh Nov 20 '19 at 8:08 • I think @Taras's question addresses the word "induce". When you get a monocolor$K_{3,3}$, do you insist to have all other edges between the six vertices to have the other color? If not, it is better to replace 'induce' by some other word. – Ilya Bogdanov Nov 20 '19 at 8:46 • @WlodAA The problem with the current formulation is that if you have a monochrome$K_6$, then you also have a monochrome$K_{3,3}$. But I suggest that asking the question you had in mind something different: there exists a copy of$K_6$whose red colored edges (say) form a subgraph isomorphic to$K_{3,3}$(and then green colored edges form two disjoint copies of$K_3$). So, which version of the question had you in mind? – Taras Banakh Nov 20 '19 at 13:33 • @TarasBanakh why should it be the same? Non-planarity is implied by a homeomorphic copy of$K_5$or$K_{3,3}\$, not isomorphic. – Fedor Petrov Nov 20 '19 at 14:14
• @WlodAA Of course, you can! – Taras Banakh Nov 21 '19 at 3:24