{"entities":{"Q1028822":{"pageid":1030670,"ns":120,"title":"Item:Q1028822","lastrevid":69640863,"modified":"2026-04-13T08:23:48Z","type":"item","id":"Q1028822","labels":{"en":{"language":"en","value":"Crossings, colorings, and cliques"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5576426"}},"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":"Q1028822$A392FCB4-792E-4D68-9CF5-3B3872DD4027","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"91000e3eaec1f4ef08f45ede8e6bb0742bc15829","datavalue":{"value":{"text":"Crossings, colorings, and cliques","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1028822$91F999FF-E5AD-4D49-A333-A95EE996967B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a599e6ad85b125db238d55958ff4b314c996f7bd","datavalue":{"value":"1182.05035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028822$4030594C-3BBB-4431-8412-D11BD1A34B47","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"82040cfe7ba0d41798d213a2940864deca0691a1","datavalue":{"value":{"entity-type":"item","numeric-id":186192,"id":"Q186192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028822$66FFE0DF-6D05-4DFA-955C-D526335251C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae41f04ca594ca85b65fe9b038c9fd67cd961e89","datavalue":{"value":{"entity-type":"item","numeric-id":311578,"id":"Q311578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028822$32D801B7-A755-4A4B-A4E0-2744B977A47D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"576bcceabff8dce115427e52f43e894dfd6284df","datavalue":{"value":{"entity-type":"item","numeric-id":290804,"id":"Q290804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028822$E4649AC8-B6E9-4C3D-89A6-78FB5EB67614","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028822$DB55AEB6-A3C8-433B-B79C-FFE63765B4A2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4b7fce5b7b399ac4add92aeecf381b606c94d340","datavalue":{"value":{"time":"+2009-07-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1028822$CCE163B9-51E5-47E1-B975-ED3FB9C068F9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"774d3a152c887e7ed4ba0a438c4fa321324fd345","datavalue":{"value":"https://arxiv.org/abs/1006.3783","type":"string"},"datatype":"url"},"type":"statement","id":"Q1028822$17B6511D-6F1B-4837-BFBC-44D0C6D69C26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"5b3bd48a9c346533da9077baa0c2c52ff4e2a2e3","datavalue":{"value":"https://eudml.org/doc/117508","type":"string"},"datatype":"url"},"type":"statement","id":"Q1028822$2CB0929E-841F-415F-9499-01625C571A41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"d968dcb8f8b1eaaafa4149a8e01d938b62f946cf","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r45.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1028822$66F12DD8-6456-4389-954D-3033C5B7531F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"025f5f9cd2cbd9063952da0fc319bdd2ff54eac3","datavalue":{"value":"Summary: \\textit{M.O. Albertson} [``Chromatic number, independence ratio, and crossing number'', Ars Math. Contemp. 1, No.\\,1, 1--6 (2008; Zbl 1181.05032)] conjectured that if graph \\(G\\) has chromatic number \\(r\\), then the crossing number of \\(G\\) is at least that of the complete graph \\(K_r\\). This conjecture in the case \\(r=5\\) is equivalent to the four color theorem. It was verified for \\(r=6\\) by \\textit{B. Oporowski} and \\textit{D. Zhao} [``Coloring graphs with crossings'', Discrete Math. 309, No.\\,9, 2948--2951 (2009; Zbl 1198.05068)]. In this paper, we prove the conjecture for \\(7 \\leq r \\leq 12\\) using results of \\textit{G.A. Dirac} [``The number of edges in critical graphs'', J. Reine Angew. Math. 268/269, 150--164 (1974: Zbl 0298.05119)]; \\textit{T. Gallai} [``Kritische Graphen. I and II'', Publ. Math. Inst. Hung. Acad. Sci., Ser. A 8, 165--192 (1963; Zbl 0121.18401), 373--395 (1963; Zbl 0144.23204)]; and \\textit{A.V. Kostochka} and \\textit{M. Stiebitz} [``Excess in colour-critical graphs'', Budapest: J\u00e1nos Bolyai Mathematical Society. Bolyai Soc. Math. Stud. 7, 87-99 (1999; Zbl 0928.05023)] that give lower bounds on the number of edges in critical graphs, together with lower bounds by \\textit{J. Pach}, \\textit{R. Radoicic}, \\textit{G. Tardos}, and \\textit{G. Toth} [``Improving the crossing lemma by finding more crossings in sparse graphs'', Discrete Comput. Geom. 36, No.\\,4, 527--552 (2006; Zbl 1104.05022)] on the crossing number of graphs in terms of the number of edges and vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1028822$B1173BAA-9448-46F9-98AE-329779C3C4C9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028822$F991E4E4-744C-4979-B555-6F1E6F7CCBDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028822$588AA49A-3A02-454D-B542-64503DE0D8E1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4a2b2452eddec244d29e21f71bb0aa73f5e41050","datavalue":{"value":"5576426","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028822$C6C3B20E-770D-492D-81C5-1B4AAB92F9F1","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":"Q1028822$0455D281-3A79-4C01-BE2A-0FE5E10C6DD1","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"475892055d00a42113395f18101356a28dfbed99","datavalue":{"value":"bafkreidflbkbmzf2aryyzgyg4hxxdwzgauucviwjsb7nmdq6yyh22hc2wa","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028822$5826C93B-E3B7-4B28-AF24-D8A73849D687","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d96668e941509127202373ec5a6be3d83d646e3","datavalue":{"value":{"entity-type":"item","numeric-id":1043657,"id":"Q1043657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bafc7fdc75559bb54667e4365482e965848274e","datavalue":{"value":{"amount":"+0.91350764","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":"Q1028822$4EDDF634-4A9C-468A-8FB3-5C98DB8A1A0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"294a85a45e8432eeea94ed25cfddb9f0a21f332b","datavalue":{"value":{"entity-type":"item","numeric-id":396914,"id":"Q396914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eddc7b143aa4d33cb02fbad6f56e7dde07c280d6","datavalue":{"value":{"amount":"+0.8994757","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":"Q1028822$F9F05EB2-40DF-47DC-AAC4-06AA07E8FBF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8840bcbb76819c6c85ae527a6b904071d143170f","datavalue":{"value":{"entity-type":"item","numeric-id":1823258,"id":"Q1823258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f6990e37eca022c7d9cadaa355ea23883faf8dd","datavalue":{"value":{"amount":"+0.89782","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":"Q1028822$849D67AD-153D-458B-AD23-21CBF870138A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53a28a6d54b659ffa697811551c921c149afc469","datavalue":{"value":{"entity-type":"item","numeric-id":3644730,"id":"Q3644730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f94fef63e629b30c0ed4446094f495e99731c584","datavalue":{"value":{"amount":"+0.89417225","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":"Q1028822$C8FE5294-8AB3-41D8-85A6-4D88C7A03E57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d473ab968b91b1ba01351b44eac5bf330f390ad","datavalue":{"value":{"entity-type":"item","numeric-id":1029072,"id":"Q1029072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0afdbc93b6cfd63b9baed2a3192bade11baa8601","datavalue":{"value":{"amount":"+0.8941456","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":"Q1028822$71D79390-B0F6-4B94-8C0E-E4CF5627103C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d92ecc0eb7d71f00626f16de8c6f6d216eccdc66","datavalue":{"value":{"entity-type":"item","numeric-id":4589364,"id":"Q4589364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"baac1ebd3e93eb95ca0c85970e035be68fb4a2cf","datavalue":{"value":{"amount":"+0.8928589","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":"Q1028822$16DAE04D-8E81-4149-9854-BA1971F04E83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61392ed04410325343d9a9e539efbd80114af3da","datavalue":{"value":{"entity-type":"item","numeric-id":4657585,"id":"Q4657585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0258c150cf04c33f3a653dac4924226b72928430","datavalue":{"value":{"amount":"+0.8885108","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":"Q1028822$6EC0900A-D57D-4E5A-94D0-0D623037CF68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4f8cc66951693de61fdca256ace2a4e87c8aa4a","datavalue":{"value":{"entity-type":"item","numeric-id":2313617,"id":"Q2313617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61754d3568879fc9709088b70e507171b89337ef","datavalue":{"value":{"amount":"+0.8878815","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":"Q1028822$8B6C0F9E-CCB6-43F6-8FFA-0C2BD11C3D4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"610f8a0190eea6e0387508f7a951a093ea95fc2b","datavalue":{"value":{"entity-type":"item","numeric-id":3697034,"id":"Q3697034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d2e515293d730ba6d3461b405eed0cf5a4690ca","datavalue":{"value":{"amount":"+0.88719517","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":"Q1028822$DEB5FA04-07FE-4A75-89DD-4D99D66A0DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"035ead674a4673c097c025125c2aab11751345f3","datavalue":{"value":{"entity-type":"item","numeric-id":4668423,"id":"Q4668423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"231a76d1a82ec015fb026718fb85cff47f1e9857","datavalue":{"value":{"amount":"+0.88711596","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":"Q1028822$05248BCA-C031-41A9-9A34-4EA9B03FB537","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Crossings, colorings, and cliques","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Crossings,_colorings,_and_cliques"}}}}}