Some remarks on Hajós' conjecture (Q707025)

Hajós' conjecture says that every graph of chromatic number at least \(k\) contains a subdivision of the complete graph of order \(k\). It is known that the conjecture is true for \(k\leq 4\) and fails for each \(k\geq 7\). Moreover it is known that the conjecture is false for almost all graphs but only few explicit counterexamples were already presented. The author discusses the relationship of this conjecture to some other conjectures and problems. Particularly he relates Hajós' conjecture to Ramsey-type problems, the perfect graph conjecture and the maximum cut problem. By an investigation of their relationships, he provides a number of new classes of explicit counterexamples to Hajós' conjecture.