MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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

share|cite|improve this question
Have you tried proving 1 at least for connected graphs? (the general case can be dealt with similarly) Where did you get stuck? In my opinion this is more suitable for math.stackexchange. – Gjergji Zaimi May 26 '12 at 2:30
Now posted at math.SE:… – Zev Chonoles May 26 '12 at 7:02
Those graphs are obtained from the Cartesian product of two graphs by considering the natural "squares" in the product and flipping a coin and deciding to delete one set of the parallel edges depending on the outcome. So a lot of those graphs will have a copy of either graphs. What I am having trouble with is coming up with an example where there are no copies. – hbm May 26 '12 at 7:16
The coin flips cannot be independent of each other, right? I multiplied two triangles and got a $3K_{2}$ - could this be right? – Felix Goldberg May 26 '12 at 7:52
Each natural "square" has its own coin flip. Duplicate edges are ignored. – hbm May 26 '12 at 8:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.