{"entities":{"Q1313834":{"pageid":1324584,"ns":120,"title":"Item:Q1313834","lastrevid":68433738,"modified":"2026-04-12T23:40:43Z","type":"item","id":"Q1313834","labels":{"en":{"language":"en","value":"Total colouring regular bipartite graphs is NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 500615"}},"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":"Q1313834$0A1315B5-04CA-423F-BBF7-E751EAF400EE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3c2592b6221cb0a1a0c31416998deddb37b9d0a3","datavalue":{"value":{"text":"Total colouring regular bipartite graphs is NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1313834$3A61F6D7-48E0-4D2A-8130-707E8DF109EC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"21a5457c9c6944e145229afda75c8ddd8ba7d2a1","datavalue":{"value":"0791.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313834$7AD76CEE-ECBA-405F-8F51-D9EB9BF2BB22","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8306aa3b18ef846655ad9c7a9fb36d97fbadcdca","datavalue":{"value":"10.1016/0012-365X(92)00058-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313834$2C8D82E5-907C-4313-891D-CFB5F09949DD","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":"Q1313834$7DB535A6-BE98-45B0-8D26-8A39B36C9360","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"03f08a3cbc69e48052a97dab7b19fd1cbcee9fe9","datavalue":{"value":{"entity-type":"item","numeric-id":1227010,"id":"Q1227010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313834$7EA0AF91-3667-4261-8904-583464A19217","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":"Q1313834$1DFA9FA5-DE09-44BD-BA86-E433B4A36E5D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ecd7f48b759dfd821149e625b4185349d418788b","datavalue":{"value":{"time":"+1994-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1313834$03DEE75F-80E1-43B4-A8C7-EB5CF0064569","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6e8b52e83e2e0438a62b499cf57c996f591a844e","datavalue":{"value":"Given a simple graph \\(G=(V,E)\\), a total coloring of \\(G\\) is an assignment of colors to the elements of \\(V \\cup E\\) in such a way that no two adjacent or incident elements receive the same color. The total chromatic number is the least number of colors in a total coloring of \\(G\\). The authors show that the problem of deciding the total chromatic number of a \\(k\\)-regular bipartite graph \\(G\\) is NP-complete for each fixed \\(k \\geq 3\\). This result strengthens an NP-completeness result by the second author. The polynomial reduction is from edge coloring and leads to bipartite gaphs with at least hundreds of vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313834$E612417E-3A49-4FFD-B7FE-45CD2A494DA3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313834$17DA2F22-0C00-4A2B-BD38-C3EFD481CC63","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313834$64FD3CFC-06FD-4A7D-86C0-02CAA4CA2BFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313834$04A91543-63C7-46A1-845E-71290BA953CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313834$ABC068C7-E89D-441D-AFA3-93B409F840A6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e9809a27a0b35d08b05edd157a1e70316962517b","datavalue":{"value":"500615","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313834$2916E1A1-19BF-48D8-9E59-A9FF968C3D7A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de797320ce0a2184cca07f3061d8f9daa48cc061","datavalue":{"value":"chromatic index","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313834$0616813B-B2FA-4606-B4DE-438D9DF7584F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10a5749cf250aeb831bc95ff6c67868b31bb5c8c","datavalue":{"value":"total coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313834$7D890965-2C41-4D87-9EF8-7DE6362A87ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"917eb44fe6d809e0bc9389e0c20d8b3e6f0da35b","datavalue":{"value":"total chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313834$7B9D986B-3144-40E9-BA56-F1C7A5CB7DD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313834$C3CBE33C-E7C8-4291-8414-1483DA2AAFF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"504d4acb38c13954552fb7b3604a634671a86fcb","datavalue":{"value":"bipartite gaphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1313834$42922D4B-5D0D-4D7B-8B3C-D57C19C44DD8","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":"Q1313834$864D727D-6C58-4282-A366-7183F01F3542","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a18decd282151f0c50f68615d322424f0bc10cb1","datavalue":{"value":{"entity-type":"item","numeric-id":5621372,"id":"Q5621372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313834$BB7E6B1A-DE79-46D6-9C09-ACC81C74E581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fac780322461a0671a545ea0d6dd54e7eb5305b","datavalue":{"value":{"entity-type":"item","numeric-id":5625208,"id":"Q5625208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313834$28800847-FD02-4559-AB96-6CF6FE5E3E63","rank":"normal"},{"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":"Q1313834$2ABC60DD-2F6B-407E-8E78-8DD38354934B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d4b26c4de03cdb3a74b663694244740fe745739","datavalue":{"value":{"entity-type":"item","numeric-id":1179463,"id":"Q1179463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313834$A54756FA-C6B8-43E5-B970-3C56FDD94A1A","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":"Q1313834$D169A896-02CA-4C4E-8A0A-215133509CA8","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":"Q1313834$EEFDD284-A4EA-4DD3-BB04-9465B6F5F7EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc4bd5b9a721234b2add0b2eb45b14f3ee4eca23","datavalue":{"value":{"entity-type":"item","numeric-id":909667,"id":"Q909667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313834$1EA02C99-E105-4194-911F-36BFDB8D3AB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d7689ee794d05f267735d01d099a85da834d533","datavalue":{"value":{"entity-type":"item","numeric-id":5564127,"id":"Q5564127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1313834$765C60D2-CD74-4532-95EA-2D287F039965","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"60cad313fda5acc3f108b47def1f3ef040b59468","datavalue":{"value":"https://doi.org/10.1016/0012-365x(92)00058-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q1313834$979F23EA-A52E-4172-B685-0910F8B682AB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"acda78eaab292b7b449062b9cb20769481e2245a","datavalue":{"value":"W1963612445","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1313834$823BE569-1B26-44B8-AFF7-93EF57B0FE57","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4331e672011f83b72bdbd98857cfc6519624798c","datavalue":{"value":{"entity-type":"item","numeric-id":909667,"id":"Q909667"},"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":"Q1313834$E25CB2DD-0598-4163-AB6A-599B7D7D0DB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20b5be279165e5dc0bdb9a2a36c7774a736d3831","datavalue":{"value":{"entity-type":"item","numeric-id":1318798,"id":"Q1318798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0e4ee51748de3b80c212285e218a3a0dd321408","datavalue":{"value":{"amount":"+0.8542380332946777","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":"Q1313834$AE5D139F-9F7B-42BA-89BA-5DFF97D7CAC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"969bcc335f6eebf38534a78afa0587c6ffc995dd","datavalue":{"value":{"entity-type":"item","numeric-id":4406072,"id":"Q4406072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0e4ee51748de3b80c212285e218a3a0dd321408","datavalue":{"value":{"amount":"+0.8542380332946777","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":"Q1313834$F7FA05CB-9018-4298-A064-B177C7BD6DBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a276c685ad8bf3e623a794f7ad1c0c30ae90d5a8","datavalue":{"value":{"entity-type":"item","numeric-id":2506359,"id":"Q2506359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf19fcb72a333b897f0174640877054b10146829","datavalue":{"value":{"amount":"+0.8119202256202698","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":"Q1313834$E0E14CBF-E673-439F-B812-9761AE511565","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":"745bbce965f9c77fef6ef7bdd454949151b877ab","datavalue":{"value":{"amount":"+0.8046113848686218","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":"Q1313834$22AB3AFF-3C26-49EE-AE2D-D8AE1657A17C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Total colouring regular bipartite graphs is NP-hard","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Total_colouring_regular_bipartite_graphs_is_NP-hard"}}}}}