1
$\begingroup$

If $G= (V(G), E(G))$ and $H=(V(H), E(H))$ are graphs.

Consider the set $\mathfrak{R}(G,H)$ of "Random Cartesian Product" whose member are graphs $K =(V(K), E(K))$ defined as follow:

$$V(K) = V(G) \times V(H)\;,$$ and if $uv \in E(G)$ and $xy \in E(H)$ then either

$$\{(u,x)(v, x), (u,y)(v,y)\} \subset E(K)\;,$$

or

$$\{(u,x)(u,y), (v,x)(v,y)\} \subset E(K)\;,$$

but not both.

  1. Is it true that if $K \in \mathfrak{R}(G,H)$, then $K$ either contains a copy of $G$ or a copy of $H$?

  2. If $\chi(G)$, $\chi(H)$ $\gt k$, what could be said about $\chi(K)$ when $K \in \mathfrak{R}(G,H)$?

  • 1
    Please mention, and provide a link, when crossposting from another site ([in this case MathOverflow](http://mathoverflow.net/questions/98011/the-set-of-random-cartesian-product-of-graphs)).2012-05-26
  • 0
    This is the first time I post here. Thanks for the reminder.2012-05-26
  • 1
    Have you tried proving these in specific cases? Where did you get stuck? As a matter of fact, have you any thoughts on the problem other than its bare statement?2012-05-26
  • 0
    @hbm: This is a nice construction and will keep me busy investigating it! I have only just found it (1/6/12) Thanks for an interesting construction. Sorry I do not have a contentful answer at this stage. herman_kretchmeyer@hotmail.co.uk There are lots of unanswered questions under the graph thoery tag. Best Regards Herman :-)2012-06-01

1 Answers 1