{"entities":{"Q974468":{"pageid":976316,"ns":120,"title":"Item:Q974468","lastrevid":65773581,"modified":"2026-04-12T05:16:43Z","type":"item","id":"Q974468","labels":{"en":{"language":"en","value":"Crossing-critical graphs with large maximum degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5716647"}},"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":"Q974468$4086E616-E8F0-44CB-9EE6-DFBE15823560","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a024266fd81bb581841ed0e9f8ddcc8aec25c0f0","datavalue":{"value":{"text":"Crossing-critical graphs with large maximum degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q974468$B71DFC81-79A0-4434-BDAD-F376492FE720","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6f99920f4c8559bcfe95907f963b16fd0bfee201","datavalue":{"value":"1247.05066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974468$A60C8B42-29AA-4B65-A0D3-FD746423815F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0344539925c30eafc8102699adfab87d48c82922","datavalue":{"value":{"entity-type":"item","numeric-id":213911,"id":"Q213911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974468$D631193B-EB06-47FD-A7D2-8AAF076F2BC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"96650f014ad2d7966e931e79230c3a74fac9c2f8","datavalue":{"value":{"entity-type":"item","numeric-id":181823,"id":"Q181823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974468$84C106A8-F0B1-4831-B2A2-C6BBABAD36B4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974468$2308DFD8-C1CF-4F2D-9A69-F96E77612A45","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c5eaf02ac47096475fa62c33f04661402608cc08","datavalue":{"value":{"time":"+2010-06-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q974468$1D2FB027-B432-49A1-9B26-88A48529C605","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"358e3928bd28346b87134dc6e06161efbcce7b60","datavalue":{"value":"https://arxiv.org/abs/0907.1599","type":"string"},"datatype":"url"},"type":"statement","id":"Q974468$724EBF78-3BFE-47A8-A43D-A01B39C3FED6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ec552716b53e601ab6046327b17c080db599b4e7","datavalue":{"value":"The crossing number of a graph is the fewest number of edge-crossings over all planar drawings. The graph is \\(k\\)-crossing-critical if its crossing number is at least \\(k\\) and deleting any edge lowers the crossing number. Label the vertices \\(v_i\\) of a graph by distinct integers \\(f(v_i)\\) and consider \\(\\max | f(v_i)-f(v_j)|\\) over all edges \\(v_i v_j\\). The bandwidth is the smallest such maximum taken over all labelings.  Richter and Salazar conjectured that any \\(k\\)-crossing-critical graph has its bandwidth bounded in terms of \\(k\\). A weaker conjecture of Richter says that its maximum degree is bounded in terms of \\(k\\). In this note the authors disprove these conjectures for every \\(k \\geq 171\\) by providing examples of \\(k\\)-crossing-critical graphs with arbitrarily large maximum degree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q974468$9A373B14-F103-4FD4-B960-9D91C1D95306","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b687a818ec58a93e77f94a71ec71ff4e2750b160","datavalue":{"value":{"entity-type":"item","numeric-id":592090,"id":"Q592090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974468$24AB0338-E123-42B7-9B4A-047822B32D62","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974468$5B8C9BC3-E53F-481B-987B-72B4B749E470","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974468$77E21AFD-9C11-4BBC-A9F5-12D55CD2F340","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974468$45A4498D-1B72-440A-97F1-97F2D2FEBF22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974468$131F3FC6-242F-45B7-8F27-AF9A93ABA262","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ce024670ac8c8930a0ce500d1d9c68b4cbbb75c6","datavalue":{"value":"5716647","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974468$450436C5-6B49-4C2F-AEFF-E406E47306F0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0bf0dbd5dd844463866c53b1b3f022210f94a95","datavalue":{"value":"crossing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q974468$79ADF803-D0C6-4AAB-99D7-F79F96CCC6BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0535553b25ad74bec70376033a310d8f41546ec","datavalue":{"value":"crossing critical","type":"string"},"datatype":"string"},"type":"statement","id":"Q974468$29DB02F0-3735-4E39-A039-3B8B098F24F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72494967642b9ea1b87091d53eb77ad552577f43","datavalue":{"value":"bandwidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q974468$5D44BCF5-3D0B-4E1C-BB79-7FFB15E7AF33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a31878d6bbe606421d6ae1acb3055851c3da8d17","datavalue":{"value":"edge crossings","type":"string"},"datatype":"string"},"type":"statement","id":"Q974468$34D4A010-F827-4596-AA6B-445C717E0C23","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":"Q974468$A56A9222-BDB5-4E58-9524-8B2F0C589789","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cfd60f2b0079e046a153291eb2e64cdd1589f4bb","datavalue":{"value":"W2083735231","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974468$6B246ACD-D7AA-4686-B1A1-A7535113B6C6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f3b6e721b1530f9d8b562f0eacc030234308db4","datavalue":{"value":{"entity-type":"item","numeric-id":5301020,"id":"Q5301020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974468$A70C395E-819E-4571-9086-1FD0F12E0319","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f2239300d67094bac25762b8043a86b62e9ae85","datavalue":{"value":{"entity-type":"item","numeric-id":1883290,"id":"Q1883290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974468$123CC6AF-9290-4E66-9982-5955CD1D58EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e661bba831f0cd014010b42c1554412db933509","datavalue":{"value":{"entity-type":"item","numeric-id":1400969,"id":"Q1400969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974468$91115837-E47A-4008-8C53-E8FD1739485A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"161ebd848d23e7712bfa94dc26f20a27c7a856b3","datavalue":{"value":{"entity-type":"item","numeric-id":1010829,"id":"Q1010829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974468$B76C2B3E-90ED-4342-AEC9-905A545E8C5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a11077841f306229a23c60c87cb2ec3b99f7f29b","datavalue":{"value":{"entity-type":"item","numeric-id":864155,"id":"Q864155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974468$E3D8C764-F863-4C0B-9DAC-EEB01A1A0D0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c0f6dd793166a567719b2fb5d958eb883aea03d","datavalue":{"value":{"entity-type":"item","numeric-id":1079583,"id":"Q1079583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q974468$30F30F60-B0A0-4B9B-88AD-C2A311597EF7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"06004127f878cfcc32b52b965f24ce009dbcdb35","datavalue":{"value":"10.1016/J.JCTB.2009.11.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q974468$EC55751E-A4F7-4EBF-AA02-CB665B9DE74E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bff65f2951671515f9c54a0e31c193127df510c3","datavalue":{"value":{"entity-type":"item","numeric-id":3069675,"id":"Q3069675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce8d8f339a0ab63806277c5a95926d8e6d09fc4c","datavalue":{"value":{"amount":"+0.883874773979187","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":"Q974468$0CBA3989-2B45-41B3-BD3E-D46F86944114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55d825f3e5e1e8d5d66fbc7af834065395b3e363","datavalue":{"value":{"entity-type":"item","numeric-id":5301022,"id":"Q5301022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f53d111b94d5a7d7fbce6b0342430472386954fd","datavalue":{"value":{"amount":"+0.8770226240158081","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":"Q974468$3094570A-0DC9-43DB-B595-ED6CB2C30679","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d65aaf8797319e516d3e6dcb186cdcea3e0151c2","datavalue":{"value":{"entity-type":"item","numeric-id":1400969,"id":"Q1400969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c150f5f8fc4c68a54979446aff037f458630d8c","datavalue":{"value":{"amount":"+0.8339546918869019","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":"Q974468$40AEB7BB-CB61-4555-BEDB-ECF11FA06E1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff25779e15b9c16ee8d707ef0f771c515972317d","datavalue":{"value":{"entity-type":"item","numeric-id":3043709,"id":"Q3043709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c150f5f8fc4c68a54979446aff037f458630d8c","datavalue":{"value":{"amount":"+0.8339546918869019","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":"Q974468$547B0BD6-1078-42CF-B47C-A58C9ADCEF57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48dfd1fc1df6e4dea1ba8c240acddf8a0141135f","datavalue":{"value":{"entity-type":"item","numeric-id":2117357,"id":"Q2117357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91c5bb92b5411fd35b046ee8d6016011e9e817a9","datavalue":{"value":{"amount":"+0.8290224671363831","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":"Q974468$CF8467F7-DB63-4E8E-9F38-9BEA485A2CA1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Crossing-critical graphs with large maximum degree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Crossing-critical_graphs_with_large_maximum_degree"}}}}}