{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T22:42:06Z","timestamp":1700001726206},"reference-count":18,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T00:00:00Z","timestamp":1219795200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2008,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In his recent work Thomassen [J Combin Theory Ser B 93 (2005), 95\u2013105] discussed various refinements of Haj\u00f3s 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 <jats:italic>m<\/jats:italic>, there exists a graph on <jats:italic>m<\/jats:italic> vertices forming a triangulation of an orientable surface so that it does not contain a subdivision of a clique of size <jats:styled-content>$O(m^{1\/2})$<\/jats:styled-content> , and its chromatic number is at least <jats:styled-content>$m^{{2\/3} + o(1)}$<\/jats:styled-content>. 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\u20133)(1995), 21\u201337] and Thomas and the first author [Random Struct Algorithms 6(1) (1995), 1\u201312]. We obtain a strengthening by replacing the \u201cnibble\u201d method by \u201crandom bites\u201d used by Alon et al. [Israel J Math 100 (1997), 171\u2013187]. \u00a9 2008 Wiley Periodicals, Inc. J Graph Theory 59: 293\u2013325, 2008<\/jats:p>","DOI":"10.1002\/jgt.20341","type":"journal-article","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T18:30:43Z","timestamp":1219861843000},"page":"293-325","source":"Crossref","is-referenced-by-count":2,"title":["Triangulations and the Haj\u00f3s conjecture"],"prefix":"10.1002","volume":"59","author":[{"given":"Vojt\u011bch","family":"R\u00f6dl","sequence":"first","affiliation":[]},{"given":"Jan","family":"Zich","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2008,8,27]]},"reference":[{"issue":"1","key":"e_1_2_1_2_2","first-page":"293","article-title":"Topological complete subgraphs in random graphs","volume":"17","author":"Ajtai M.","year":"1979","journal-title":"Studia Sci Math Hungar"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02773639"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00215-I"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122551"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90062-5"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-27.1.85"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1947-08785-1"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579269"},{"key":"e_1_2_1_11_2","unstructured":"G.Haj\u00f3s \u00dcber eine Konstruktion nichtn\u2010Farbbarer GraphenWiss Zeitschr Martin Luther Univ Halle\u2010Wittenberg 10 (1961) 116\u2013117."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/040617765"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050041"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","first-page":"N15","DOI":"10.37236\/1982","article-title":"Triangulations and the Haj\u00f3s' conjecture","volume":"12","author":"Mohar B.","year":"2005","journal-title":"Electr J Combin"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.56021\/9780801866890"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060102"},{"key":"e_1_2_1_17_2","volume-title":"Random Graphs","author":"\u0141uczak T.","year":"2000"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1052"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.005"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.20341","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.20341","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T22:19:06Z","timestamp":1700000346000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.20341"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8,27]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["10.1002\/jgt.20341"],"URL":"https:\/\/doi.org\/10.1002\/jgt.20341","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8,27]]}}}