Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

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

share|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
1  
Now posted at math.SE: math.stackexchange.com/questions/149960/… –  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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.