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

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.

share|improve this question

1 Answer 1

At http://jdc41.user.srcf.net/useful/sparse-ramsey.pdf there is a set of lecture notes from a course given by Imre Leader in 2003. On page 18 of these notes this is given as an open problem.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.