Triangulations and the Hajós conjecture

In his recent work Thomassen [J Combin Theory Ser B 93 (2005), 95–105] discussed various refinements of Hajós conjecture. Shortly after Mohar [Electr J Combin 12 (2005), N15] provided an answer to Thomassen's Conjecture 6.5, and proposed a possible extension. The aim of this article is to address Mohar's suggestion. In particular, we prove that, for infinitely many integers m , there exists a graph on m vertices forming a triangulation of an orientable surface so that it does not contain a subdivision of a clique of size $O(m^{1/2})$ , and its chromatic number is at least $m^{{2/3} + o(1)}$ . The main part of the proof is to show that the random graph can be almost covered by oriented triangles which do not contain certain forbidden configurations. We use a technique similar to the ones of Archdeacon and Grable [Discrete Math 142(1–3)(1995), 21–37] and Thomas and the first author [Random Struct Algorithms 6(1) (1995), 1–12]. We obtain a strengthening by replacing the “nibble” method by “random bites” used by Alon et al. [Israel J Math 100 (1997), 171–187]. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 293–325, 2008