4

1

It is known that for any graph H and all $k∈N$, there exists a graph $G$ such that any $k$-coloring of the edges of $G$ yields a monochromatic copy of H and ω(G)=ω(H) (the two graphs have the same clique numbers).

My question is: Given any graph $H$ with finite girth, is there a $G$ with the same girth as $H$ such that any $2$-coloring of the edges of $G$ yields a monochromatic copy of $H$?

I think this is an open problem but if someone can confirm that and give some references concerning this I would be most obliged.

flag

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.