MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

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|cite|improve this question

Here 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|cite|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.