On a coloring conjecture of Hajós (Q5964996)

Hajós' conjecture states that graphs, which do not contain the subdivisions of \(K_5\), are 4-colorable. Another result by \textit{X. Yu} and \textit{F. Zickfield} [J. Comb. Theory, Ser. B 96, No. 4, 482--492 (2006; Zbl 1091.05030)] state that any minimum counterexample to Hajós' conjecture, if exists, must be 4-connected. Based on these results, the authors prove in this article that if \(G\) is a minimum counterexample to Hajós' conjecture and \(S\) is a 4-cut in \(G\), then \(G-S\) has exactly two components. This is the only result discussed in this manuscript and its proof is very lengthy, but really beautiful and interesting. The proof is a case to case analysis. The proof consists of many steps and subcases. An outline of the proof is as follows. By assumption, \(G\) is a minimal graph such that it does not contain any subdivision of \(K_5\) and is not 4-colorable also. Let \(S\) be a 4-cut in \(G\) and \(C_1,C_2,\ldots, C_k\) be the distinct components of \(G-S\). The set \(H_i\) be the induced graph \(G[V(C_i)\cup S]\), for \(1\leq i\leq k\). In the first step, it is proved that \(H_s\cup H_t-v_r\) has no cycle containing \(S-\{v_r\}\), provided \(1\leq s, t\leq k\) (with \(s=t\) when \(k=3\)) and for \(1\leq r\leq 4\). In the second step, the authors prove that the only possible value of \(k\) is \(3\). (Therefore, \(s=t\) also). In the third step, it is proved that the induced graph \(G[S]\) has at most one edge. In the fourth step, by considering possible three subcases, authors establish that for \(l\in \{1,2,3\}\), the set \(\{x\in S: d_{H_l}(x)\geq 2\}\) consists of at most \(2\) elements. In the fifth step, it is proved that \(H\) has no subdivisions of \(K_5\). Since \(H\) has no subdivisions of \(K_5\), then, by Hajós' conjecture, \(H\) is 4-colorable. The 4-coloring \(c:V(H)\to \{1,2,3,4\}\) of \(H\) can be viewed as a 4-colouring for \(H_2\), \(H_3\) as well. The authors try to extend this coloring to \(G\) also, by considering all the three possible cases and at each step, arrive at a contradiction and finally conclude that \(c(v_1)=1, c(v_2)=c(v_3)=c(v_4)=2\), indicating the fact that \(G\) has exactly 2 components. The authors really deserve much appreciation in providing such detailed, comprehensive proof for the only theorem in the document.