Budapest Problem Exchange in MathematicsProblem                             No. 3

Area: Graph theory, infinite graphs

Title: Embedding 4-chromatic graphs into two uncountably chromatic graphs

Problem Description: Is it true that if tex2html_wrap_inline20tex2html_wrap_inline22 are uncountably chromatic graphs, then there is a 4-chromatic graph H embeddable into both ?

Background: This is well-known with "3-chromatic" in place of "4-chromatic" as it is known that every uncountably chromatic graph contains every long enough odd circuit.

Contact person: Péter Komjáth (

Posted by: Vince Grolmusz (

Originated from: Paul Erdõs