{"entities":{"Q679741":{"pageid":681590,"ns":120,"title":"Item:Q679741","lastrevid":63664602,"modified":"2026-04-11T14:42:53Z","type":"item","id":"Q679741","labels":{"en":{"language":"en","value":"Thickness and colorability of geometric graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6827953"}},"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":"Q679741$6A247C38-2F94-4E48-8632-F847240E48A8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6fd0ab38b7f2f0751d73e31c5166513600106f2e","datavalue":{"value":{"text":"Thickness and colorability of geometric graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q679741$F7CA7641-1C97-4C96-B462-0AC61768CD82","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5e8b653b1ece077eb43602d9100e4b91feac924c","datavalue":{"value":"1384.05086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q679741$505E49D5-1182-4C13-A190-CC486198BA3D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3e9bd1bfb140e662e6ea0631b6d3b66c5e782e0","datavalue":{"value":{"entity-type":"item","numeric-id":181833,"id":"Q181833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$F7019C8B-4CD2-49C3-8E27-4077BDF1D899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e302c703f96a0f15b85a7a84a84d6b5e5365ed96","datavalue":{"value":{"entity-type":"item","numeric-id":181834,"id":"Q181834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$F61869A3-AE29-4F04-A767-3BCDB3ECAAF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b3b9cc1f159c37a4e5a1bbc7a4f2ae91d3150fc7","datavalue":{"value":{"entity-type":"item","numeric-id":396680,"id":"Q396680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$86A25256-9A79-4A72-8202-1C5778736EC7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$BE4AC6EB-96DE-48B5-A332-8FD3D05F169E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3706de551438a6e783012180a02b770ee4195f88","datavalue":{"value":{"time":"+2018-01-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q679741$A81097BC-E89A-470D-815E-3103D87B87B9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"407293d3e188296f6ccf6436270a12235239f741","datavalue":{"value":"The authors consider the thickness and geometric thickness of graphs. They give an example of a graph with thickness equal to 2 and geometric thickness equal to 3. They prove that the problem of recognizing geometric thickness is NP-hard even for graphs with geometric thickness equal to 2. Moreover, they give the proof of NP-hardness of \\((4t-1)\\)-coloring graphs with geometric thickness \\(t\\). The paper improves known results in this topic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q679741$6E826D07-1BF2-4DD2-A963-D08E02580140","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"aee79d242f75af733e0d4fce649011872d9aabae","datavalue":{"value":{"entity-type":"item","numeric-id":298965,"id":"Q298965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$2C0DFD02-6FEA-4040-BC25-56BB86FAC487","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q679741$C9947F61-7E1F-4D42-B597-FBCF1DA2F9EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q679741$F7192EBF-ABC5-470A-B9F7-441B5CEF2036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q679741$0251EDD1-3EF4-448F-AB83-9D080C1B61C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q679741$3C520181-7A23-4DC7-AA61-9769B4D89A38","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a82d7528e28f1299571cd97b82e0733b16c9a0b5","datavalue":{"value":"6827953","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q679741$767F1491-61B5-47C5-8689-49BB548F4FED","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f2bd7369831d9e54b4e511b9d71ba97d1e383ac","datavalue":{"value":"complete graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q679741$22F52F7A-EF3A-4920-B7D1-A2D72515C456","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db1e62ec3b97650496f80b6a2641132dc076b2ff","datavalue":{"value":"geometric thickness","type":"string"},"datatype":"string"},"type":"statement","id":"Q679741$E2A47796-869E-4BC0-AD11-AC9FA0030183","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q679741$04EFCF5A-EBAC-4448-96AA-00B7AACD99EE","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":"Q679741$04EA2723-EC6C-49D5-BECE-BA2ACD50B27E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f835d5ac7cae8a6861cc0f020c2f0c64c6f4f843","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2016.03.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q679741$D1ACAE54-5E11-406C-BFCC-C7BB8DC1B4CF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"45fc3d0cf4ec8adc377e04408b6cab7454f0a214","datavalue":{"value":"W2302259827","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q679741$F8FE7F7D-E4F0-4A6D-9D5A-7E155CF51EFB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab8a76a633cda4e85d630342fb5d1776053acae7","datavalue":{"value":{"entity-type":"item","numeric-id":2864305,"id":"Q2864305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$F0141964-EABC-419A-A682-A73FF66E6F5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f03cd132f9b96528a007d6ca8ce3f3ee3ad92e4c","datavalue":{"value":{"entity-type":"item","numeric-id":5735733,"id":"Q5735733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$F21D458B-8A54-4633-8A7A-C57820BBB455","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e1bbfe35d6a1f371dd2f4ef8a3059849dd602a1","datavalue":{"value":{"entity-type":"item","numeric-id":4159090,"id":"Q4159090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$0E546F23-570A-4D52-BBF4-988D7A6D27C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e82170a9f17dbc1083aa16cd57fe1c408cd8f4a","datavalue":{"value":{"entity-type":"item","numeric-id":5732335,"id":"Q5732335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$D1970E80-856F-4F79-8A1B-782C50883E96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"230ee840aa43d445e4dcb3e6d52443db304efd05","datavalue":{"value":{"entity-type":"item","numeric-id":4511256,"id":"Q4511256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$E3DB57CE-998D-4CA9-8CC0-40FD0894BE74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d901276bc7ac785f5a216e4482ca42f03c5458a","datavalue":{"value":{"entity-type":"item","numeric-id":3969882,"id":"Q3969882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$86C9F17E-78B6-4BCD-8CAC-D5515D75EB0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b65b4ea8f5b5b71e41bdde3be23a3f1bc2189048","datavalue":{"value":{"entity-type":"item","numeric-id":1385299,"id":"Q1385299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$47E29A34-8C53-4B1B-8B8E-C59F2686E010","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c054052e4d99ea3cb2f01faac0ba0f5434524d4","datavalue":{"value":{"entity-type":"item","numeric-id":4657580,"id":"Q4657580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$CEC26E14-67BD-4E97-AFD9-0DAF371A714F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"761744477615703d81228c12c7f42ab4ec7c9241","datavalue":{"value":{"entity-type":"item","numeric-id":1961382,"id":"Q1961382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$88771DBE-190D-4FD4-8A0B-4292FC553526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c05c8242afaa42aaf4f288b3de9f5445058fea81","datavalue":{"value":{"entity-type":"item","numeric-id":2583678,"id":"Q2583678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$4C583122-63CA-4747-A6FB-FDD40C3D376A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d0017cba81eb9e6d377dbb857cb5114197168f5","datavalue":{"value":{"entity-type":"item","numeric-id":5361688,"id":"Q5361688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$2B509D02-C2B1-4598-A660-59F79BD61A5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eeaf99789dde00d9e62d7457c0579f1960be478e","datavalue":{"value":{"entity-type":"item","numeric-id":2369933,"id":"Q2369933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$5B637651-3F57-4F58-A1B0-E677808E83E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"588f8ce49af7d61830d214c3184ba368c65f9753","datavalue":{"value":{"entity-type":"item","numeric-id":621923,"id":"Q621923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$E5838FB3-6EED-4ED9-9ADB-7839C6681367","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74422792d32c65046465ade61e1ba80c4aa3185a","datavalue":{"value":{"entity-type":"item","numeric-id":2561601,"id":"Q2561601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$50B9231A-00C5-4745-8A34-C87989E16057","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5659184edf0e5fe73903990b4844a7b79bda62d","datavalue":{"value":{"entity-type":"item","numeric-id":5896917,"id":"Q5896917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$39007D1D-4B2E-420C-B6B9-F66087E74128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86187cd049bd6565ddbc4e21f37dc55f378bee76","datavalue":{"value":{"entity-type":"item","numeric-id":1250223,"id":"Q1250223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$5CC461D7-4C7D-473D-B159-30F27682EDD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35184f581a4fa42ee779b59d5e27eea0c204219f","datavalue":{"value":{"entity-type":"item","numeric-id":5931450,"id":"Q5931450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$47DBA040-8D37-4169-A467-4FF244A06B54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e070cbf7ef73d43587f9701677ea364ef44fe4c","datavalue":{"value":{"entity-type":"item","numeric-id":476435,"id":"Q476435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$FE0761D9-977D-4AFF-BF7F-A7ABCD3700B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a92b1590c48020e117dea7abe33e060affff5baa","datavalue":{"value":{"entity-type":"item","numeric-id":1863073,"id":"Q1863073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$D928E06A-FBB8-4F67-BDF7-9203A3F78B07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49ad2ea320e978548ca0da09d0f95363bf06f18e","datavalue":{"value":{"entity-type":"item","numeric-id":5301376,"id":"Q5301376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$7EA07D4D-4156-4A6E-A2F6-5A6F5FEF2A2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"708f8ca93e2a412d51cbf640b639925e6a4f6ab6","datavalue":{"value":{"entity-type":"item","numeric-id":3442763,"id":"Q3442763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$2890D458-089C-4794-B075-E67B2176E627","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a2ad71c908ed96c861e693d071c375d8d1b0c13","datavalue":{"value":{"entity-type":"item","numeric-id":2959757,"id":"Q2959757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q679741$DD2C1FC9-C2E0-4283-8036-FB18DF0F5D43","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9e83db2c0483188a4b335bdd6da5970050f50534","datavalue":{"value":"10.1016/J.COMGEO.2016.03.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q679741$5332FFDE-3A49-437F-8C17-9DED4197CEB6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9325521fbb2054beb0a36ff319a605cc02738d39","datavalue":{"value":{"entity-type":"item","numeric-id":2864305,"id":"Q2864305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ef2c1d16041c11cc00d29c3f0bdf073e795d36f","datavalue":{"value":{"amount":"+0.9935908317565918","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":"Q679741$4DAB80B5-9111-43BD-BAC9-1B6E9BB5868C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f5b5026480c150e8f1c72527603e6b3de484628","datavalue":{"value":{"entity-type":"item","numeric-id":4511256,"id":"Q4511256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"068cf4c9e2ea4bb9f38177d57c8f9f9f6920bb5e","datavalue":{"value":{"amount":"+0.8229543566703796","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":"Q679741$A95BA100-7E6E-4681-A4B9-69AC8E350B05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71bb1f0e5d7c2037d6a5f425aa2ec5ca2bdf3a05","datavalue":{"value":{"entity-type":"item","numeric-id":2583678,"id":"Q2583678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88fe9d6ce39a6e5c02afce9e96970276f96d9c1c","datavalue":{"value":{"amount":"+0.8217228651046753","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":"Q679741$DEB2C2AB-8466-43A6-826C-09F1AFA64441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6898683358abe54169b808cd25d267e375021e0","datavalue":{"value":{"entity-type":"item","numeric-id":621923,"id":"Q621923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1222a1375eb3e78a04cc61f5c047a95f536c49ba","datavalue":{"value":{"amount":"+0.8035315871238708","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":"Q679741$7EA11DC0-70DF-489F-96E1-36D9F4C0E1BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba96fca40690e38215ca6f8839b4f5d22228269c","datavalue":{"value":{"entity-type":"item","numeric-id":5361688,"id":"Q5361688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b9ba053884a205b9bc8008b891cbf5db6a6c4c5","datavalue":{"value":{"amount":"+0.7940642833709717","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":"Q679741$BB88A2D3-9E47-4D66-A59B-31D838AA4A7D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Thickness and colorability of geometric graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Thickness_and_colorability_of_geometric_graphs"}}}}}