{"entities":{"Q760439":{"pageid":762288,"ns":120,"title":"Item:Q760439","lastrevid":42678233,"modified":"2025-07-08T09:54:47Z","type":"item","id":"Q760439","labels":{"en":{"language":"en","value":"Lower bound of the Hadwiger number of graphs by their average degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3884189"}},"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":"Q760439$237C34A8-5BF2-4EF1-8D37-7C9ACB14B292","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"abb3295f7d8959df7a8433f49e33c9d547edecd3","datavalue":{"value":{"text":"Lower bound of the Hadwiger number of graphs by their average degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q760439$9CDB24EE-3AEC-48BF-AF4F-F8B3A9FB3A66","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1b8d8f085fb270c788a2eed2467e2e22862727ad","datavalue":{"value":"0555.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760439$93BA7CFA-6C6F-4A59-B429-6E6182E64A65","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5ad718cdc29c5c61afea017d682e66113fb9fa77","datavalue":{"value":"10.1007/BF02579141","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760439$964F3AF2-3262-4758-B45B-9EC45166D6A9","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":"Q760439$9653D541-3DA3-404E-AF5A-2D6A7C8F6477","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q760439$3832745A-8BC4-43DD-959E-0EFA2AA5D232","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"17f8439e0c62a81e965c9326c4edf9094ecdfaee","datavalue":{"value":"A contraction of a connected graph \\(G=(V,E)\\) to the complete graph with r vertices is considered as a surjection \\(\\psi: V\\to \\{1,2,...,r\\}\\) with the properties that every subgraph of G induced by \\(\\psi^{-1}(i)\\) is connected and for any integers i, j from \\(\\{\\) 1,2,...,r\\(\\}\\), \\(i\\neq j\\), there exist vertices \\(v\\in \\psi^{-1}(i)\\) and \\(w\\in \\psi^{-1}(j)\\) such that \\((v,w)\\in E.\\) the greatest r such that G can be contracted onto the complete graph with r vertices is called the Hadwiger number \\(\\eta\\) (G) of G. The minimum of \\(\\eta\\) (G) for graphs \\(G=(V,E)\\) with \\(| E| /| V| \\geq k\\) is denoted by \\(\\eta\\) (k). Further for each positive integer k the function \\(w(k)=\\min \\{\\eta (G): \\chi (G)\\geq k\\}.\\) The well- known conjecture of Hadwiger says that \\(w(k)=k\\) for any k.    In the present paper it is proved that \\(\\eta (k)\\geq k/270\\sqrt{\\log k}\\) and \\(w(k)\\geq k/540\\sqrt{\\log k}\\) for \\(k\\geq 2\\). From this corollary follows that if k is large enough, then Hadwiger's conjecture is true for almost all graphs with n vertices and kn edges.","type":"string"},"datatype":"string"},"type":"statement","id":"Q760439$5213C1A9-5577-4303-9E67-1978AA8CDEB0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760439$16FE4C3F-CCFE-4485-96DF-0C36D8EBAAAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760439$6F53C7FE-5365-4508-BFE4-C6ED992800C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760439$FE40BADD-EC14-44ED-8EF3-119F3320F02F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"36dc89f17740977b7123f3da6891b984b63aade1","datavalue":{"value":"3884189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760439$E79C54CD-9C63-4E73-9BBF-66FE0EEAB5F2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4605262f950382e87dc58df46038532164191769","datavalue":{"value":"contraction","type":"string"},"datatype":"string"},"type":"statement","id":"Q760439$893839DE-F48A-408A-B061-C259C9EC80E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f2bd7369831d9e54b4e511b9d71ba97d1e383ac","datavalue":{"value":"complete graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q760439$D0F6246B-1A44-4E73-8FBB-8DACA34429AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c9c8f71d65ed49c53e6795d80a29937931e5df3","datavalue":{"value":"Hadwiger number","type":"string"},"datatype":"string"},"type":"statement","id":"Q760439$AED59BF7-F817-4660-8A6A-0EE62C0AF9C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdefb28951ee63f397ce9368bae3e97a2589921e","datavalue":{"value":"Hadwiger's conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q760439$8FCDB7FB-3766-4779-AADC-982C9BEBE3E3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a112fcddf40de3e0f26627c12549da4365ccc05","datavalue":{"value":{"entity-type":"item","numeric-id":214987,"id":"Q214987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760439$96FBA71D-74BA-4365-B5EC-616A51E84068","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d9b462d071c33d7d83486f9fef57845bb41d7acf","datavalue":{"value":{"entity-type":"item","numeric-id":190573,"id":"Q190573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760439$490D7F1F-588D-41EB-A5DD-9999D3562B00","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":"Q760439$80F5ED4C-A3DD-4E52-9C13-A4ABACB552A8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a775b5e8da902c4d2ada0b9ccba768c403ce36d5","datavalue":{"value":"Q56235110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760439$727F4E7F-669F-4B56-98F6-88AC602B80DB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"631afda92da774b2f35528b579855e622332ed35","datavalue":{"value":{"entity-type":"item","numeric-id":4065548,"id":"Q4065548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760439$107E869B-D794-4423-A0EE-742EC072811E","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":"Q760439$2FC6DA96-0A63-4D44-83D2-368B92C15CB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aaf3c4e561ff9c595c12a93f9e25ef45438f889e","datavalue":{"value":{"entity-type":"item","numeric-id":3726155,"id":"Q3726155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760439$8BBE2F09-339C-4395-A960-0111C302B938","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea616e9dd0eb45550b5668e6f36bc1c263756556","datavalue":{"value":{"entity-type":"item","numeric-id":2530192,"id":"Q2530192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760439$DF369AE5-FE27-4408-957D-7BBE88B06532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9473d4b83aecec379a206a3aa3be759945e7b2af","datavalue":{"value":{"entity-type":"item","numeric-id":1246435,"id":"Q1246435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760439$4AD3EDE9-9C1A-48DB-BA01-01BDF6A6685F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"451cbb39afc126b40f7b3c239c65e065b043391a","datavalue":{"value":{"entity-type":"item","numeric-id":2538210,"id":"Q2538210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760439$B04A2642-C90E-40EA-B8FB-BA5F7CFAC4A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"452c281303465b29f22fa014edde2e31c22c9a76","datavalue":{"value":{"entity-type":"item","numeric-id":5670653,"id":"Q5670653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760439$BBF4492A-D521-43C3-9FC3-826924C9D1D9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a0bb0e84edffe7c9bdbd10c1573390af46f145a8","datavalue":{"value":"https://doi.org/10.1007/bf02579141","type":"string"},"datatype":"url"},"type":"statement","id":"Q760439$298B631D-87D2-4FAE-A780-2EF093F3A490","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"69bc5517d604ea1d11e57509b95716ee671a4f50","datavalue":{"value":"W2047993669","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760439$AFEE7E37-5A5E-4824-B5E9-4D21C2433A0C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3d2de05f19e4447a29a0906d4e2fbefb6729277","datavalue":{"value":{"entity-type":"item","numeric-id":2975718,"id":"Q2975718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93a32f71d9e3a6f7fff7d7f0d69971afa845d667","datavalue":{"value":{"amount":"+0.93551147","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760439$F45FD61B-D5AB-45CE-8E7A-422486EC55B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ff188bb5877b8cf036f2c919562ac08d6e96214","datavalue":{"value":{"entity-type":"item","numeric-id":5497164,"id":"Q5497164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f3504baad9b49f7272b5f8216f1cdf6129b8047","datavalue":{"value":{"amount":"+0.9277358","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760439$01278206-0860-4AD3-BCB4-E324C08E7625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a8fbac30c42b260fd7faac53edbfd123c2bb359","datavalue":{"value":{"entity-type":"item","numeric-id":2954366,"id":"Q2954366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"003ecf206f7d9e6b32b6e566b160ac1b83366994","datavalue":{"value":{"amount":"+0.92648673","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760439$FA20B1E0-D1CB-451D-A64B-5C7FCC3AE1D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a8a7692e3a9b280af07e47a1ac30328a3a0d97f","datavalue":{"value":{"entity-type":"item","numeric-id":5377838,"id":"Q5377838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd7c02f06f459d61a74807de69cc21cedee15e08","datavalue":{"value":{"amount":"+0.9193584","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760439$9A91A487-D9F2-48B8-BF73-0F2CFA08A133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86ce673f22ca498b5709b3464b6363f2794a8274","datavalue":{"value":{"entity-type":"item","numeric-id":2664553,"id":"Q2664553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25aef5d05af459995f1458f4985273feebe0808b","datavalue":{"value":{"amount":"+0.9154411","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760439$E068B427-CD69-4441-92A0-6C7FE9E0DA3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7918358a9ce9d2d5f2759eca1c29d9d47c42c507","datavalue":{"value":{"entity-type":"item","numeric-id":2975669,"id":"Q2975669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"563394018af2f85cc8fff940bc0ab306fb64ceea","datavalue":{"value":{"amount":"+0.9131303","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760439$FCC2BC29-AC52-41E6-AB8E-E44CD4C4F9D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3886c1c6ed409d3ff45edc1a0fabff04d696a036","datavalue":{"value":{"entity-type":"item","numeric-id":3726155,"id":"Q3726155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"298b6d6219da9c23b268e8341df67cf3386171e9","datavalue":{"value":{"amount":"+0.9114916","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760439$5606B4CB-D5ED-4A25-AD9B-493603F7A257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93ead115ed16fd7589686ecab4ecb089c200e33b","datavalue":{"value":{"entity-type":"item","numeric-id":1714768,"id":"Q1714768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53df3f9af41736130fbfdd707c41ed1611249916","datavalue":{"value":{"amount":"+0.9106677","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760439$C37F5245-C3D9-4148-BA9C-B9180D3A9F04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6482030f1ad7290576fc15ef18c6c613b1072bb6","datavalue":{"value":{"entity-type":"item","numeric-id":3333070,"id":"Q3333070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"adcc395a28eed9e46b9afd76725dc3683ec6a845","datavalue":{"value":{"amount":"+0.9104099","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760439$13755A84-C086-4E38-8CE7-B2B2BAF244DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f1e6cb6298e4aece90ae58e30e119ce0270a1ca","datavalue":{"value":{"entity-type":"item","numeric-id":556830,"id":"Q556830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4a564abbff052efa8341e8529db2b2e385157b7","datavalue":{"value":{"amount":"+0.9064758","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q760439$6E410378-2020-4F51-9B72-00B6EB9C27DB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:760439","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:760439"}}}}}