Proof of Toft's Conjecture: Every Graph Containing No Fully Odd K4 is 3-Colorable

K. Appel and W. Haken, “Every planar map is four colorable,” A.M.S. Contemp. Math., vol. 98, 1989. P. Catlin, “Hajós graph-coloring conjecture: Variations and counterexamples,” J. Combin. Theory Ser. B, vol. 26, pp. 268-274, 1979. V. Chvátal, “On certain polytopes associated with graphs,” J. Combin. Theory Ser. B, vol. 18, pp. 138-154, 1975. G.A. Dirac, “Aproperty of 4-chromatic graphs and some remarks on critical graphs,” J. London Math. Soc., vol. 27, pp. 85-92, 1952. A.M.H. Gerards, “Homomorphisms of graphs into odd cycles,” J. Graph Theory, vol. 12, pp. 73-83, 1988. A.M.H. Gerards, “A min-max relation for stable sets in graphs with no odd-K 4,” J. Combin. Theory Ser. B, vol. 47, pp. 330-348, 1989. A.M.H. Gerards and A. Schrijver, “Matrices with the Edmonds-Johnson property,” Combinatorica, vol. 6, pp. 365-379, 1986. H. Hadwiger, “Über eine klassifikation der streckenkomplexe,” Vierteljahrsch. Naturforsch. Ges. Zürich, vol. 88, pp. 133-142, 1943. G. Hajós, “Über eine konstruktion nicht n-färbbarer graphen,” Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, vol. 10, pp. 116-117, 1961. T.R. Jensen and F.B. Shepherd, “Note on a conjecture of Toft,” Combinatorica, vol. 15, pp. 373-377, 1995. T.R. Jensen and B. Toft, Graph Coloring Problems, John Wiley & Sons, Inc., 1995. U. Krusenstjerna-Hafstrøm and B. Toft, “Special subdivisions of K 4 and 4-chromatic graphs,” Monatsh. Math., vol. 89, pp. 101-110, 1980. L. Lovász, “Some finite basis theorems in graph theory,” in Combinatorics II, A. Hajnal and V.T. Sós (Eds.), Colloq. Math. Soc. Janos Bolyai, North-Holland: Amsterdam, 1986, vol. 18, pp. 717-729. N. Robertson, P. Seymour, and R. Thomas, “Hadwiger's conjecture for K 6-free graphs,” Combinatorica, vol. 13, pp. 279-361, 1993. N. Robertson, D. Sanders, P. Seymour, and R. Thomas, “The four-colour theorem,” J. Combin. Theory Ser. B, vol. 70, pp. 2-44, 1997. E.C. Sewell and L.E. Trotter, “Stability critical graphs and even subdivisions of K 4,” J. Combin. Theory Ser. B, vol. 59, pp. 74-84, 1993. P. Seymour, Oral Communication. C. Thomassen and B. Toft, “Non-separating induced cycles in graphs,” J. Combin. Theory Ser. B, vol. 31, pp. 199-224, 1981. B. Toft, “Problem 10,” in Recent Advances in Graph Theory, Proc. of the Symposium held in Prague, June 1974, M. Fiedler (Ed.), Academia Praha, 1975, pp. 543-544. B. Toft, “75 Graph-coloring problems,” in Graph Colorings, R. Nelson and R.J. Wilson (Eds.), Longman Scientific and Technical, Wiley, 1990. K. Wagner, “Über eine eigenschaft der ebene komplexe,” Math. Ann., vol. 114, pp. 570-590, 1937.