On the Hajós number of graphs (Q1970708)

A graph \(G\) is said to have property \(P_m\) if it contains neither a subdivison of a complete graph \(K_{m+1}\) nor a subdivison of a complete bipartite graph \(K(\left\lfloor \frac m2\right\rfloor +1,\left\lceil \frac m2\right\rceil +1).\) \textit{G. Chartrand, D. Geller}, and \textit{S. Hedetniemi} [J. Comb. Theory, Ser. B 10, 12-41 (1971; Zbl 0223.05101)] conjectured that, for any \(n,m\) with \(m\geq n\geq 1\) \((m\geq n\geq 2)\), the set of vertices (edges) of any graph having the property \(P_m\) can be partitioned into \(m-n+1\) sets such that each of these sets induces a graph with property \(P_n.\) It is shown in the paper that there exists a positive constant \(c\) so that both conjectures fail for \(m>cn^2.\)