{"entities":{"Q909667":{"pageid":911515,"ns":120,"title":"Item:Q909667","lastrevid":65304645,"modified":"2026-04-12T01:40:16Z","type":"item","id":"Q909667","labels":{"en":{"language":"en","value":"Determining the total colouring number is NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4137786"}},"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":"Q909667$6B2187A2-CC95-4FA4-9A42-15B2C63DE465","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fa3a4b57261f48a488cacc21055b0d51ca83e684","datavalue":{"value":{"text":"Determining the total colouring number is NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q909667$E8CC402A-BE31-494C-805A-AF4BE6C06D4C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"626994ffbd994cb9e04319c4269a25ca5f2d1e42","datavalue":{"value":"0695.05023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909667$D49B24D9-2ED8-44FD-9E2A-407A75507E22","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c0341ff9e8d4fd728ed1ee9bffeb9f4093ba5038","datavalue":{"value":"10.1016/0012-365X(89)90187-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909667$A529A7C9-B03C-4F34-8357-7D74D5602445","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6e2df2c578ffe58f85dc9ec0207164bb33072b4d","datavalue":{"value":{"entity-type":"item","numeric-id":686498,"id":"Q686498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909667$8F772909-990F-48B3-B857-D27034AB239E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909667$18C59874-4A80-48F8-B81B-1DCA7BA6AE35","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q909667$81661DC4-A753-49E7-A9BC-09FFC1BB87A0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dc598db2b5b77a3ed50c99c42062e54ed9eb21de","datavalue":{"value":"\\textit{D. Leven} and \\textit{Z. Galil} proved that [``NP-completeness of finding the chromatic index of regular graphs'', J. Algorithms 4, 35-44 (1983; Zbl 0509.68037)] the problem of determining the chromatic index of an arbitrary r-regular graph for \\(r\\geq 4\\) is NP-complete. The present author proves that a 4-regular graph G is 4-edge colourable if and only if another cubic bipartite graph H is 4-total colourable. Hence the problem of determining the total chromatic number of an arbitrary cubic bipartite graph is also NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q909667$3D5C1B69-2B01-411B-AEDA-0544257EC90D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909667$D65AC5DC-BE3C-4DD0-84C9-AE6C7B14FBF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909667$5DFA33A0-A972-4811-A271-01FD394E8FC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909667$4129FE1A-6501-4DC6-9A29-977CC0F14F2E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f1f360356848cb8bff0db1e191fd31a68c21d370","datavalue":{"value":"4137786","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q909667$099CDF9A-D095-42A9-9133-FCDA609E24D2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc653b6a31dcd73ff0c82a090d57852e65c2467f","datavalue":{"value":"total colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q909667$C8997A5F-0129-4C27-8DA3-92873675E052","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c57b92affcb004309363ec03a950a06a95694e2f","datavalue":{"value":"edge-colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q909667$A411C413-2403-4978-90D1-A3F18BF759F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"917eb44fe6d809e0bc9389e0c20d8b3e6f0da35b","datavalue":{"value":"total chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q909667$12AFA4B9-5703-47F8-9B60-E88E7E7669B9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0dfbdb0929ddc22bcd5bd1c182b95d3875d4d630","datavalue":{"value":{"entity-type":"item","numeric-id":1164054,"id":"Q1164054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909667$B4730D15-CB23-4F98-A3BB-63C5712B535A","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":"Q909667$E8B949C0-04FE-410B-BFB1-6F056449E76F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909667$16460D41-B269-4F74-A8D6-5050272A323A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909667$B1827022-CB24-439F-9901-F89BBC6F2602","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b3de5d933aac98ce001a35d32a88fd2111d286a","datavalue":{"value":{"entity-type":"item","numeric-id":4747513,"id":"Q4747513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q909667$06364B20-B080-437B-BC4B-E75BAA096DC3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cb2e4e5646fea61835cdc1a427bb6a957313482","datavalue":{"value":{"entity-type":"item","numeric-id":1313834,"id":"Q1313834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42b27c185d84c63a86c54e7fa56eb2bc5e731f60","datavalue":{"value":{"amount":"+0.9096556305885316","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":"Q909667$F392E820-F88C-4E5D-AE83-6311E50C9501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91b1a9e0ef83650a25f470943a30eda11c06ce22","datavalue":{"value":{"entity-type":"item","numeric-id":1173977,"id":"Q1173977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6c548a1ada96a02e37356609e9bdb22d34a888a","datavalue":{"value":{"amount":"+0.847980260848999","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":"Q909667$24726B5D-2ADD-441B-B6A1-F4E591F7C775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1db29ce8d4cb8d5411a3ad4d350957e2ff9ea191","datavalue":{"value":{"entity-type":"item","numeric-id":4033261,"id":"Q4033261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a5991fa7fb5e21f277f1f4e2b205f64fff9517e","datavalue":{"value":{"amount":"+0.8459678292274475","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":"Q909667$62C840CA-2268-494F-81AD-9FF8A1615553","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24678519c91afdca719e5537484100d1170838d3","datavalue":{"value":{"entity-type":"item","numeric-id":1354146,"id":"Q1354146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"329af1af5771550744680c79d6b94d2e46541979","datavalue":{"value":{"amount":"+0.8263132572174072","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":"Q909667$B084ADD9-BBD8-40ED-AA32-0BF861DDD77C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b283db389854c407fb618171a70b3f47beb8fe8e","datavalue":{"value":{"entity-type":"item","numeric-id":3503456,"id":"Q3503456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6abf4f2833d75d51d55be627bc401c46f0b7364c","datavalue":{"value":{"amount":"+0.8100254535675049","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":"Q909667$2E1AD6BC-6682-4334-964C-6D04A7428915","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Determining the total colouring number is NP-hard","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Determining_the_total_colouring_number_is_NP-hard"}}}}}