{"entities":{"Q6636987":{"pageid":14248139,"ns":120,"title":"Item:Q6636987","lastrevid":99931484,"modified":"2026-06-05T21:02:16Z","type":"item","id":"Q6636987","labels":{"en":{"language":"en","value":"On 3-coloring circle graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7942892"}},"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":"Q6636987$C7159764-AEE2-414A-8F22-F2EE2465FE2F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dc0ce85ad806fdda382bc3d8733f8ba19a6f0d06","datavalue":{"value":{"text":"On 3-coloring circle graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6636987$3E87FF05-410C-4A36-BD2B-C8A193FC3B75","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"13a28c2153d032abd5917732ec3258be72e94ba1","datavalue":{"value":{"entity-type":"item","numeric-id":6560145,"id":"Q6560145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$E6BB4E0E-DEF9-4B11-801D-31F8EA0D3B19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"49bbe852f04b340afb483710d250633e3c669542","datavalue":{"value":{"entity-type":"item","numeric-id":306262,"id":"Q306262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$F9E9B0E6-7F8F-411D-A9F9-A35072B48BDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"02e01d4d731738171fb2b6cf82665cbad426221a","datavalue":{"value":{"entity-type":"item","numeric-id":1709529,"id":"Q1709529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$9FB2EF01-40ED-4333-BE8B-329E2EE9018C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ddcc97f8715cbdd96dafedab0ed9ed6cebddf843","datavalue":{"value":{"entity-type":"item","numeric-id":2701745,"id":"Q2701745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$1BEE434B-D382-4133-ABDD-39BD37F02AF3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"60fa3f87d97ee0a9686c2e5537009cd3455d3ea2","datavalue":{"value":{"time":"+2024-11-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6636987$1ACACD70-0A38-4B84-AAB0-38018284DB41","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7aa2ddd5f2840b074892e577c071c5cecc651f91","datavalue":{"value":"Finding a \\(k\\)-coloring for a circle graph is known to be NP-complete for \\(k \\ge 4\\) and trivial for \\(k=1,2\\). In 1992, \\textit{W. Unger} [Lect. Notes Comput. Sci. 577, 389--400 (1992; Zbl 1494.68204)] claimed to have an efficient algorithm that finds a 3-coloring in \\(O(n\\log n)\\) time if it exists. Much of the detail for Unger's paper is in his PhD thesis, which is in German [\\textit{W. Unger}, F\u00e4rbung von Kreissehnengraphen (Coloring of circle string graphs). University of Paderborn, Germany (PhD Thesis) \\N(1990)]. Here the authors argue that there are errors in Unger's algorithm, both in the transformation of the 3-coloring problem to a satisfiability problem and with empirical evidence that exhibits a runtime behavior that is not consistent with the claimed running time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6636987$A33B15DC-9C31-49B0-935E-B20FAA4864FF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c373609087678f84cf49ac586680a31002124e72","datavalue":{"value":{"entity-type":"item","numeric-id":267204,"id":"Q267204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$3FE7D52F-A96C-483C-8E7E-97305313C33D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6636987$093B4A8E-052A-4791-881C-8293E3B41E07","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f2e2c95d11bc6806f7354834d2ec1d402bbd5dcd","datavalue":{"value":"7942892","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6636987$9A554842-46B0-4AA6-AA2C-64C35584AB52","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6636987$7A6C1572-7F88-4130-AD6E-164D8774810C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20a5e1f1191acc6a9fe899dae84da95c86beb92d","datavalue":{"value":"circle graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6636987$051D5B50-7387-40A5-8F61-97E25221F126","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":"Q6636987$5A0D19FC-AC39-46B1-81B2-BCF033081D88","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5f21db9d5219c937310ed15d0b79df6e1434523","datavalue":{"value":{"entity-type":"item","numeric-id":450560,"id":"Q450560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$CF24704E-7DFF-4C83-8C24-610BFAB0EE37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9621055264f5c2969343cb09962887cb0c101779","datavalue":{"value":{"entity-type":"item","numeric-id":5710814,"id":"Q5710814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$B5BBFB82-D94E-4542-83F9-41FCAA332FBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6eac35406a0efc1d23196c34748be2caefee9975","datavalue":{"value":{"entity-type":"item","numeric-id":5120157,"id":"Q5120157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$501083F7-10EB-4710-B1D1-E768DD3CAE79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b602d01a898344ce4e168ea2188a5d94cd04e17","datavalue":{"value":{"entity-type":"item","numeric-id":4727445,"id":"Q4727445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$8210F77B-6490-4664-9D04-92899B622EEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31004528a7ad0ceb29dd33e08eb7822698600930","datavalue":{"value":{"entity-type":"item","numeric-id":4667621,"id":"Q4667621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$441F21A6-4A24-4ACD-8954-162E61D50B9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2a3d4c88e49f9f0f6960f4fdd4648b5bb3e174f","datavalue":{"value":{"entity-type":"item","numeric-id":1748996,"id":"Q1748996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$BE0E47EE-033A-4A11-8BAC-774032FC0487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"571568dd0064272acc2b7fcdcd3767f1e9d64d00","datavalue":{"value":{"entity-type":"item","numeric-id":3787505,"id":"Q3787505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$122CFA22-EAB8-49D9-9EBF-ACA1F9324ED6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68b71d344f7b09014bca8372570b7d51e77599b4","datavalue":{"value":{"entity-type":"item","numeric-id":4002519,"id":"Q4002519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$A8531FDE-4C91-431B-85C1-C7DA5C371FA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99e37ba3e7198cc73c3365bd827b0c0b9aa52d14","datavalue":{"value":{"entity-type":"item","numeric-id":5096797,"id":"Q5096797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$FDD22758-11E0-4430-A7E2-73D51AB3785D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd05e4b67b3a31abf197ae994d88fff07d3dbdbb","datavalue":{"value":{"entity-type":"item","numeric-id":1120582,"id":"Q1120582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$314BB468-D0CB-434B-8B34-2F3AE1657747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8abbcff456ce20502a384f26bff78a05500a351e","datavalue":{"value":{"entity-type":"item","numeric-id":2200923,"id":"Q2200923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$4728946E-9B5D-4C96-BFCF-07F7CC029FCB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1629a20bcf8a4a3cb764e7dba82aa5973d0a6247","datavalue":{"value":"10.7155/JGAA.V28I1.2991","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6636987$AACB259E-EA79-4E0E-9781-F6C1C732A318","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"839278b1dbfc7c997047188af22902ad10857ef4","datavalue":{"value":{"entity-type":"item","numeric-id":5096797,"id":"Q5096797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97ef5f947acff6857d73a39aa3d69b638003f2d6","datavalue":{"value":{"amount":"+0.8154222369194031","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":"Q6636987$6D992838-745C-454D-A655-765707CA4987","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d06c958a118cc1a094f8ba5b4afccf5bb22bf144","datavalue":{"value":{"entity-type":"item","numeric-id":3787505,"id":"Q3787505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f08704336192066c5e962d30568c7a6d7d7c7763","datavalue":{"value":{"amount":"+0.7966408133506775","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":"Q6636987$A9479552-D2BA-45BC-BD1F-D0648973F781","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"706d893d603189e138f5ad118e026676a619a415","datavalue":{"value":{"entity-type":"item","numeric-id":3737469,"id":"Q3737469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"128aeb9ed7232a3bbd4e74c62ab793d3ada52937","datavalue":{"value":{"amount":"+0.711873471736908","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":"Q6636987$C57E16A7-440E-4BA1-84F2-8BEB13A755A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c76c16fd957c90b367b5d5389482f8ccd50b7ed","datavalue":{"value":{"entity-type":"item","numeric-id":4002519,"id":"Q4002519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a064779cbf44f874f0cfa28a7b765303a3e5f80","datavalue":{"value":{"amount":"+0.708846390247345","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":"Q6636987$66E03578-E38B-4E37-AACB-F431889E3BE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd8f04820e5f83647bcbeb798885c3a789b7f9cc","datavalue":{"value":{"entity-type":"item","numeric-id":3503503,"id":"Q3503503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce10b7f550b7c102b9113bf1b78caf6145e451bf","datavalue":{"value":{"amount":"+0.7085255980491638","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":"Q6636987$192E1C1F-0D25-46A3-A72C-280D4132E96C","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6636987$72E19848-B0E0-47A4-A1F5-94D133F7AD7B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On 3-coloring circle graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_3-coloring_circle_graphs"}}}}}