10
$\begingroup$

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.

$\endgroup$

1 Answer 1

8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.