{"entities":{"Q1192946":{"pageid":1203695,"ns":120,"title":"Item:Q1192946","lastrevid":69859989,"modified":"2026-04-13T10:49:40Z","type":"item","id":"Q1192946","labels":{"en":{"language":"en","value":"The complexity of some graph colouring problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 61819"}},"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":"Q1192946$834E93C1-9B0A-4D96-84D2-B1C5E4065366","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"191c8c773a6738d269c407ba590ea32a9beb7e32","datavalue":{"value":{"text":"The complexity of some graph colouring problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1192946$16EE1680-39C4-4448-A1C7-05320FA2B4EA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8e2f7c45fa1a38b04af07b99a05841d2af4077e1","datavalue":{"value":"0758.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192946$7273E9D7-6E0F-4296-87EE-7E04C2A00562","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3d65145e5e2d23f49fc20f51dace09724baad96e","datavalue":{"value":"10.1016/0166-218X(92)90227-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192946$9C9D1756-5B97-4837-A372-A716FCF0EC0B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192946$4E9A3691-0D9B-4989-B834-992BB2B7E1AE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1192946$AB299805-C8F4-4452-93C3-46C6816F3373","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7da266243ef3dbe4bf474694a768d143dc91a22c","datavalue":{"value":"This paper deals with the following two problems. The first is on the complexity of counting colourings of a degree fixed graph. The author shows that provided the maximum degree and the number of colours are both allowed to be at least 3, then counting the number of colours is \\(\\#P\\)- complete even if the graph is restricted to be regular and bipratite. The second is on the colourability of graphs on fixed surfaces. The author establishes a linear time algorithm for determining the \\(k\\)-colourability of a graph on a fixed surface for \\(k\\geq 6\\) fixed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192946$D345B271-BA5C-4C43-B0DA-54E229A99AAB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f4aed06ce87e48c8c58fd5d268ea91779fe40edf","datavalue":{"value":{"entity-type":"item","numeric-id":176697,"id":"Q176697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192946$2BB5A88B-1E7B-46D6-8148-1E2D2FF17D01","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192946$D37743EA-07A2-4E4F-896F-3305FA28C9B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192946$31D9933E-D751-4C50-8530-45B7F23F2C3A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ab792f0d84eecab466640fe1f419b89d2c78848e","datavalue":{"value":"61819","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192946$5B4A935B-76F6-4C2D-BBEF-869FC3DB70E1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7af855c1fc958abeba13cfe70b4d38557bfd8baa","datavalue":{"value":"computing complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192946$F7826BF3-035F-40A6-8362-A5ACF0E8AA4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"def48283d510794913c58f78056b808e00633a5c","datavalue":{"value":"graph colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192946$D947C2C7-F39F-4196-AD45-C076B9A74F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f39d7fc3fc364a43a70204f0de54dd2c811a56b","datavalue":{"value":"surface","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192946$51EDF528-DED6-4579-9864-100B336B7337","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192946$08181512-7545-4DC3-87F4-1CFF98F89FCA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a6e1f9ad498b53f98afc6a2f82e96c5f4554c2c2","datavalue":{"value":{"entity-type":"item","numeric-id":383737,"id":"Q383737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192946$8FE8EE6C-72D4-41C1-A52E-02A8E0FB3357","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":"Q1192946$619939E9-1DB0-4C4D-A004-B3CEEB0F4B0C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192946$786A1DB5-F73D-4E01-B76A-1D0FF9B4325B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a92ab907df072bb20a1057061523b1fdda43679","datavalue":{"value":{"entity-type":"item","numeric-id":5782525,"id":"Q5782525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192946$671AF571-7DC5-4C67-8E64-FB0AC173CCD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4936c8c7796b21c7564f5704ca23fd312d5ff05","datavalue":{"value":{"entity-type":"item","numeric-id":3798668,"id":"Q3798668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192946$FE41C40E-4F20-4A51-9C6A-C41AE4087454","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a32ad8cbf357b329b5c6fb5bd73d59aac0d93e81","datavalue":{"value":{"entity-type":"item","numeric-id":1079363,"id":"Q1079363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b57946992be5845534bdf94d3502f47adcedaf17","datavalue":{"value":{"amount":"+0.8415976762771606","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":"Q1192946$725B769C-373F-4EA5-9DA6-47AC91A10716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ddbc42caeae41a2e04ca7f6195a68d34ce134a0","datavalue":{"value":{"entity-type":"item","numeric-id":1186161,"id":"Q1186161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d6b1c385082a58ba6a4c7bd1e96832eb932c840","datavalue":{"value":{"amount":"+0.8316524624824524","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":"Q1192946$46FF0662-FC13-493C-B125-AA98D384CB18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"068de292421424c3d0dbafa52cc761b8d5bd08d9","datavalue":{"value":{"entity-type":"item","numeric-id":1579552,"id":"Q1579552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26327dc2ad1fe4690b60edde719a3dab8ee8546e","datavalue":{"value":{"amount":"+0.8224144577980042","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":"Q1192946$C9880C28-F9D9-48EF-A591-3013D85CEAF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77bf84c9a82caafe68c12a39a4437ca01601c373","datavalue":{"value":{"entity-type":"item","numeric-id":5479031,"id":"Q5479031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26327dc2ad1fe4690b60edde719a3dab8ee8546e","datavalue":{"value":{"amount":"+0.8224144577980042","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":"Q1192946$07F5ACE1-7254-42B5-B993-69FB6895C827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d80436a7f2f690412ffc3c00684c219eb54ee6e","datavalue":{"value":{"entity-type":"item","numeric-id":3758852,"id":"Q3758852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b3fbd922733f0491f71062737895d1b14bfac1a","datavalue":{"value":{"amount":"+0.8184948563575745","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":"Q1192946$137C3958-3A9B-4F87-A979-EF4D2FA3176E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of some graph colouring problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_some_graph_colouring_problems"}}}}}