sagt aus, daß für r ∈ N jeder Graph, dessen chromatische Zahl mindestens r beträgt, eine Unterteilung des vollständigen Graphen K_r der Ordnung r als Teilgraphen enthält.

Für r< 4 ist die Hajós-Vermutung äquivalent zur entsprechenden Aussage der Hadwiger-Vermutung und damit richtig.

In ihrer allgemeinen Form wurde die Hajós-Vermutung bereits 1979 von P.A.Catlin widerlegt. Der Satz von Erdos-Fajtlowicz sagt aus, daß sogar fast alle Graphen Gegenbeispiele zur Hajós-Vermutung sind.