Can we color the edges of any graph $G$ on $2m-1$ vertices with two colors such that any induced subgraph with at least $m$ edges is non-monochromatic?

If true, this would be sharp as shown by the star $K_{1,2m-1}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.