5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Observe that $RK_{xx}\le R(5,5)\le 48. The is a conjecture that R(5,5)=43. $\endgroup$ – Taras Banakh Nov 20 '19 at 8:08
  • 2
    $\begingroup$ 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. $\endgroup$ – Ilya Bogdanov Nov 20 '19 at 8:46
  • 1
    $\begingroup$ @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? $\endgroup$ – Taras Banakh Nov 20 '19 at 13:33
  • 2
    $\begingroup$ @TarasBanakh why should it be the same? Non-planarity is implied by a homeomorphic copy of $K_5$ or $K_{3,3}$, not isomorphic. $\endgroup$ – Fedor Petrov Nov 20 '19 at 14:14
  • 1
    $\begingroup$ @WlodAA Of course, you can! $\endgroup$ – Taras Banakh Nov 21 '19 at 3:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.