# “Random Cartesian Product” of graphs

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)$?

-
Please mention, and provide a link, when crossposting from another site (in this case MathOverflow). –  Zev Chonoles May 26 '12 at 7:02
This is the first time I post here. Thanks for the reminder. –  hbm May 26 '12 at 7:18
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? –  Did May 26 '12 at 7:20
@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 :-) –  Herman Jun 1 '12 at 15:21

We prove the first item by induction on $n=|E(G)|$ the number of edges in $G$.

$n=0$: trivial.

$n=1$: $E(G)=\{(u,v)\}$. Let $K\in\mathfrak{R}(G,H)$. Two cases:

• either $\forall (x,y)\in E(H)$ $\{((u,x)(u,y)), ((v,x)(v,y))\} \subset E(K)$ then $K$ contain a copy of $H$.

• or, $\exists (x,y)\in E(H)$ $\{((u,x)(v,x)), ((u,y)(v,y))\} \subset E(K)$ then $K$ contain a copy of $H$.

$n\to n+1$: Suppose the property true for all graphs such that $|E(G)|=n$. Let $G$ be a graph with $|E(G)|=n+1$, let $K\in\mathfrak{R}(G,H)$. Let $E'$ be such that $E(G)=E'(G)\cup\{(u',v')\}$ and $|E'(G)|=n$, let $G'=(V(G),E'(G))$. We define $K'$ as the sub graph of $K$ where we removed all the edges $((u',x),(v',x))$. It's easy to see that $K'\in\mathfrak{R}(G',H)$.

By induction hypothesis either $K'$ contains a copy of $H$, and since $K'$ is contained in $K$, $K$ also contains a copy of $H$. Or, $K'$ contains a copy of $G'$. Let $x'\in V(G)$ be the element shared by all the nodes of this copy. Two cases:

• either, $((u',x'),(v',x,))\in V(K)$ then there is a copy of $G$ in $K$.
• or, $((u',x'),(v',x,))\notin V(K)$. By definition of $K$ that mean $\forall (x,y)\in E(H), \{((u',x),(u',y)),((v',x),(v',y))\}\subset E(K)$ that means there is a copy of $H$ in $K$.

Hence in all cases there is either a copy of $H$ or a copy of $G$ in $K$.

For the second item, by using the first item we know that $\chi(K)\geq\chi(H)$ or $\chi(K)\geq\chi(G)$ hence $\chi(K)\geq k$.

-