Proof of Toft's conjecture: Every graph containing no fully odd \(K_4\) is 3-colorable (Q1273432)

If each edge of \(K_4\) is subdivided into a path of odd length, the resulting graph is called a fully odd \(K_4\). In 1974 \textit{B. Toft} [Recent Adv. Graph Theory, Proc. Symp. Prague 1974, 543-544 (1975)] conjectured that every graph containing no fully odd \(K_4\) is 3-colorable. This would strengthen a result of \textit{G. A. Dirac} [J. Lond. Math. Soc. 27, 85-92 (1952; Zbl 0046.41001)] that every graph containing no subdivision of \(K_4\) is 3-colorable. \textit{T. R. Jensen} and \textit{F. B. Shepherd} [Combinatorica 15, No. 3, 373-377 (1995; Zbl 0832.05038)] confirmed Toft's conjecture for line graphs. The present author proves the conjecture in general, and conjectures that a polynomial-time algorithm exists for recognizing graphs with no fully odd \(K_4\).