{"entities":{"Q1835686":{"pageid":1846428,"ns":120,"title":"Item:Q1835686","lastrevid":48669100,"modified":"2026-01-05T13:45:51Z","type":"item","id":"Q1835686","labels":{"en":{"language":"en","value":"On the conjecture of Hajos"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3794117"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835686$EC5DAB42-C0DF-4945-9024-7933F61CB065","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e90f45fc4452e3c287657a98642bdfff266e09dc","datavalue":{"value":{"text":"On the conjecture of Hajos","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1835686$72506C3E-53DC-4EBD-927E-BF148BE652F0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ca96977f613a803fbf74c5b5e39559c1177b6d2a","datavalue":{"value":"0504.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1835686$69652F08-629C-415B-863E-760D74A3F517","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b4c74aa87079fe416bfa94ee5d54ec11d9891a7c","datavalue":{"value":"10.1007/BF02579269","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1835686$3B9EBCAA-079F-462B-80EE-F04A5F507DCF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"051bf00170fa159b13bb2c6ef6e30d035206773d","datavalue":{"value":{"entity-type":"item","numeric-id":912654,"id":"Q912654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835686$F3DCA5D6-40A9-43C1-A28E-B9C6EB5E6ED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb00475fd567190194461a0f087df1793eeae7c4","datavalue":{"value":{"entity-type":"item","numeric-id":6480801,"id":"Q6480801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835686$AA3D5503-3699-42A4-8856-A49D3E647E38","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835686$E037A5E7-5EB2-4A3B-BE52-DCC799466642","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"50fad0db7dc87cb4e51866acdb5ccbaa54ec857b","datavalue":{"value":{"time":"+1981-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1835686$FE02853B-519D-449E-98D7-C786D747F04E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aaa22eb8bf4e234fc9eb8d2215cac3353abafb40","datavalue":{"value":"\\textit{G.Haj\u00f3s} [Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturw. Reihe 10, 113-117 (1961; Zbl 0094.17602), pp. 116-117] conjectured that every \\(s\\)-chromatic graph contains a subdivision of \\(K_s\\), the complete graph on \\(s\\) vertices. This conjecture was disproved ins a paper by \\textit{P.A.Catlin} [J. Comb. Theory, Ser. B 26, 268-274 (1979; Zbl 0385.05033)]. In the present paper it is shown by probabilistic methods that the Haj\u00f3s conjecture fails for almost all graphs. More precisely, let \\(G=G(n)\\) be a graph of \\(n\\) vertices. Denote by \\(\\chi(G)\\) the chromatic number of \\(G\\) and by \\(\\sigma(G)\\) the largest integer \\(\\ell\\) such that \\(G\\) contains a subdivision of \\(K_{\\ell}\\). Put \\(H(G)=\\chi(G)/\\sigma(G)\\) and \\(H(n)=\\max_{G(n)}H(G(n))\\) (hence, the Haj\u00f3s conjecture says \\(H(n)=1\\)). In the present paper it is shown that there exists an absolute constant \\(c\\) such that \\(H(n)> C\\sqrt n/\\log n\\) holds for almost all labelled graphs with \\(n\\) vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1835686$CCB90DE5-3A94-4BCB-9B2E-6EA901EEB8C2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1835686$1CE6CB97-9DAD-4435-8DB7-CE4487069473","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1835686$CF099578-41A7-455A-9B7A-BF9446EBDD9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1835686$94977106-CADF-4E52-8301-F8EA72A31669","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"de3eb91103387875e7ece5492c4b6524837f4063","datavalue":{"value":"3794117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1835686$9F1C4A8C-65F4-46C6-B5E6-90419DF2FE05","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba14d9b831bbea33be0644a3b55147bb6975b45f","datavalue":{"value":"s-chromatic graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1835686$68EA382A-B245-4CF0-A326-1B43DDB0F851","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1835686$00F2A29E-C972-4A98-B3A5-57490F68BDD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d959bd733318746098f9611a2534b0fcaba0c1f","datavalue":{"value":"subdivision","type":"string"},"datatype":"string"},"type":"statement","id":"Q1835686$9EC7AB3E-8A7F-4486-BD8D-596980953766","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04efd67b0a8c0b41a9b59d1875c6f7e1514a0278","datavalue":{"value":"labelled graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1835686$01336542-1910-410A-AA97-85358402EC76","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7586b293c42ef5d48a614ec3acbed180cd36cf97","datavalue":{"value":"Q105709214","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1835686$C7DB4F94-48EF-4C97-9498-7958E180D2A3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bccf737338fb4df11281b54a4bafbc562a37369c","datavalue":{"value":{"entity-type":"item","numeric-id":587654,"id":"Q587654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835686$A3B8E60C-AA4B-462B-BDCA-449E08A2F2B2","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835686$06575019-8BEE-46CF-8011-90C277CA92FA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"42ddca71e564bf3e7c0c23c34fa9f4deeb35ed68","datavalue":{"value":{"entity-type":"item","numeric-id":1223318,"id":"Q1223318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835686$F8757670-06B2-48A3-A96E-D76049C1EEF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85cfa63f67ed3743ed6d983c37c02f4185c5f671","datavalue":{"value":{"entity-type":"item","numeric-id":5811782,"id":"Q5811782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835686$C76672D2-E945-49D4-BF04-92578E69364E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fca512bd62ef81317baaf07336a09e35ab66e1e","datavalue":{"value":{"entity-type":"item","numeric-id":5789964,"id":"Q5789964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835686$94E29656-02B7-4D36-A240-0E86FC5DD021","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67085864f6a7b39588c06ae975acc511fd0f7ad6","datavalue":{"value":{"entity-type":"item","numeric-id":3872499,"id":"Q3872499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835686$3999F54D-D808-405A-8956-A03C7E50064D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9752745e0bf5079a46b3df4174fa00ba27470b0","datavalue":{"value":{"entity-type":"item","numeric-id":5837979,"id":"Q5837979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835686$68A414DE-67F0-4C20-A34F-EECB7BECDE80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2df3e44f1c43aece3bdd69ab8baa271c3e83135a","datavalue":{"value":{"entity-type":"item","numeric-id":1255499,"id":"Q1255499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1835686$ACBACA46-3F23-4663-9C2D-E73A7ECA4283","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f1112d1a52b6f148b893988f00aab6251243ff1c","datavalue":{"value":"https://doi.org/10.1007/bf02579269","type":"string"},"datatype":"url"},"type":"statement","id":"Q1835686$4FC8935D-E770-4D9C-AD5E-FCA9A8019E98","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e9a577206f9e0c2646664e35eab5ecf64709786e","datavalue":{"value":"W2034615466","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1835686$1DF82B7C-5D7C-4EC8-BEC9-420D24E9778F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4dbdbe1a98d259f4d392f2b1af7c6aff7664c38","datavalue":{"value":{"entity-type":"item","numeric-id":707025,"id":"Q707025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0dba552105243a38af3f891b085d3a1976d0e4f9","datavalue":{"value":{"amount":"+0.9104262590408324","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1835686$549CE3C5-7130-4E32-9C8E-3F0668E4F678","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d8c20b6c89fb248805a166833170b29a7d39558","datavalue":{"value":{"entity-type":"item","numeric-id":2448966,"id":"Q2448966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3e4fe6997180a79ff49c1da1704e0ede657545f","datavalue":{"value":{"amount":"+0.8938115835189819","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1835686$4905CC36-32F7-4060-8668-8BE173F9B5CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7eb83d5c2b7ff07ec74427cedb50abdfb984cf1","datavalue":{"value":{"entity-type":"item","numeric-id":5921669,"id":"Q5921669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7cd75bc066582f1fc49d8af238836aeb82cdc8e","datavalue":{"value":{"amount":"+0.8702118992805481","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1835686$8AA4B36C-06FB-4F2C-8E6D-1223559A9F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7374e2ba8c85aeca9a570b9df98a3968e1ec45e","datavalue":{"value":{"entity-type":"item","numeric-id":858687,"id":"Q858687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acbc3a9c3635c27817b2fd1eb5a15f49ad1d81fe","datavalue":{"value":{"amount":"+0.863543689250946","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1835686$AA911505-28C9-4B73-8345-F3A017058960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86faac7eb812ed2c4754b32812110849db08d5f5","datavalue":{"value":{"entity-type":"item","numeric-id":5964996,"id":"Q5964996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04bec174964aa83c4da86d33edc037d99a443b34","datavalue":{"value":{"amount":"+0.8561172485351562","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1835686$E4D87D5E-D0A4-4C31-8D6E-A38FCFC6C012","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1835686","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1835686"}}}}}