{"entities":{"Q2094863":{"pageid":2105606,"ns":120,"title":"Item:Q2094863","lastrevid":78256343,"modified":"2026-05-06T11:09:45Z","type":"item","id":"Q2094863","labels":{"en":{"language":"en","value":"Vizing's and Shannon's theorems for defective edge colouring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7613656"}},"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":"Q2094863$B5B57D2A-6449-477D-84F8-2F58D362EB3A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3be937ac2b830ea433763604d3ae8790be667c6b","datavalue":{"value":{"text":"Vizing's and Shannon's theorems for defective edge colouring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2094863$7DF0BDAE-40D0-4985-90BC-218F00EA6300","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d9e56022fe9bcc51869a6ca847aae4ca37b8dfc3","datavalue":{"value":"1503.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094863$1FF65B5D-E77E-47EC-BEEE-75D8ECD91673","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8d362cd38eeaf326b85dfbdd38458971887df5c6","datavalue":{"value":"10.37236/11049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094863$9704751C-A87A-4FFE-9EB2-7D78A755C3C1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"70c605789c19a2a2efdb859996933424e0bf2b34","datavalue":{"value":{"entity-type":"item","numeric-id":312154,"id":"Q312154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$AE6A0E11-5C45-4195-9C7A-DEC27E9271D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d029b13c7318beeff3927780b2a6a2866274e8df","datavalue":{"value":{"entity-type":"item","numeric-id":2094862,"id":"Q2094862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$5FCB70C8-92DD-466F-BDA5-CD151F427B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"87577e543b62bb41b26df7a4f1fb494459866729","datavalue":{"value":{"entity-type":"item","numeric-id":270028,"id":"Q270028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$43441558-9B92-4D1C-AF63-1A568A164823","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$AAF85A57-EC17-43A2-84AD-4C8447FB1704","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"41c2d4b2b9eee3d1d4724659108ff6928154d594","datavalue":{"value":{"time":"+2022-11-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2094863$41DCF593-D77A-4CCD-A553-A6E173A4BDBF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d081a26a679982dc792eed93570ff7cda612e123","datavalue":{"value":"https://arxiv.org/abs/2201.11548","type":"string"},"datatype":"url"},"type":"statement","id":"Q2094863$168C5B56-9D39-4C58-9FD2-CCBED46C17C5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d60b95ac58f42742d41ef917459d47f63a3c8068","datavalue":{"value":"Summary: We call a multigraph \\((k, d)\\)-edge colourable if its edge set can be partitioned into \\(k\\) subgraphs of maximum degree at most \\(d\\) and denote as \\(\\chi^\\prime_d(G)\\) the minimum \\(k\\) such that \\(G\\) is \\((k, d)\\)-edge colourable. We prove that for every odd integer \\(d\\), every multigraph \\(G\\) with maximum degree \\(\\Delta\\) is \\((\\lceil \\frac{3\\Delta - 1}{3d - 1} \\rceil, d)\\)-edge colourable and this bound is attained for all values of \\(\\Delta\\) and \\(d\\). An easy consequence of Vizing's Theorem is that, for every (simple) graph \\(G, \\chi^\\prime_d(G) \\in \\{\\lceil \\frac{\\Delta}{d} \\rceil, \\lceil \\frac{\\Delta+1}{d} \\rceil\\}\\). We characterize the values of \\(d\\) and \\(\\Delta\\) for which it is NP-complete to compute \\(\\chi^\\prime_d(G)\\). These results generalize classic results on the chromatic index of a graph by \\textit{C. E. Shannon} [J. Math. Phys., Mass. Inst. Techn. 28, 148--151 (1949; Zbl 0032.43203)], \\textit{I. Holyer} [SIAM J. Comput. 10, 718--720 (1981; Zbl 0473.68034)], \\textit{D. Leven} and \\textit{Z. Galil} [J. Algorithms 4, 35--44 (1983; Zbl 0509.68037)] and extend a result of \\textit{O. Amini} et al. [``Frugal colouring of graphs'', Techn. Rep. RR-6178, Institut National de Recherche en Informatique et en Automatique (2007)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094863$174185AE-EBBC-4993-822C-6138E363537D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094863$DA12C6C3-C79D-4B49-9D28-3869C82AB327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094863$168A6444-AA13-4B6A-BBE9-1E30EBD75DB8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"50d0764ff7e972ad77295484fba9b801a5aef618","datavalue":{"value":"7613656","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094863$126EB0ED-0D59-488D-8FAB-B24489946064","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b7ec189301a6f71dd89a0f40a76920074da5cfe","datavalue":{"value":"\\((k, d)\\)-edge colourable multigraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094863$0AF47968-16E2-46C6-836E-20330C54507F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9995f2ff850ba2e785f2733f4e8a6970ffc49212","datavalue":{"value":"Vizing's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094863$D16CCB2D-2843-4482-AD35-B530CBEC33BA","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":"Q2094863$2C3673B0-1950-4A7F-9B93-580D3A0342CD","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"200cc7bec26acd6bcb7032493da0f253038808dc","datavalue":{"value":"Q114988522","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094863$ED0FC2F7-0379-4B32-9EE2-48F8FDF604F7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f5c14a3a1c470c79c032a58e59dd9f0ee356ea8c","datavalue":{"value":"W4306653310","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094863$7627A69D-5CA6-4F71-88D7-86BD1615BBA6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"24d08bc2309a916fa5b15e17e5aaa34154a3fe61","datavalue":{"value":{"entity-type":"item","numeric-id":547467,"id":"Q547467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$8EB5851A-DB4B-4C9D-B708-BEBC62F68781","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e38b99d1be6c0610d08ee28d2550597f6c390fc1","datavalue":{"value":{"entity-type":"item","numeric-id":5198063,"id":"Q5198063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$678B9F91-7C6D-4850-BB88-A8E130C2ED84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb8b23be685b19bdd0313eaaa79ce5140147fe55","datavalue":{"value":{"entity-type":"item","numeric-id":1366604,"id":"Q1366604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$46F2A12C-AF4A-435E-AC46-BD6FDC0B310A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d423a5b14f2f898348796b44407743a1d8d3c679","datavalue":{"value":{"entity-type":"item","numeric-id":4056033,"id":"Q4056033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$86FB7DDF-20B3-4E3C-9260-E82FCE7C0B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"018fc0ca7a9cf2c5ba47f43ef4277dcf1f33c43c","datavalue":{"value":{"entity-type":"item","numeric-id":5937593,"id":"Q5937593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$4A7C172F-3D63-4B5D-B34E-EBC45F3CA482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e34de45c9d4bd4c2f35a453de8b907622e14a6d2","datavalue":{"value":{"entity-type":"item","numeric-id":1366607,"id":"Q1366607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$426DB897-0274-4C87-B210-390A74D3511F","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":"Q2094863$93854B7C-EA4A-40F9-8419-F292C7DE97E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"640cc7cad469b8c1a227d69ac0ab63a8a0341518","datavalue":{"value":{"entity-type":"item","numeric-id":3337508,"id":"Q3337508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$6A9D2400-FA59-4E3A-8304-9E7A2A4AACF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27ae0e2c3e78f79383a07c48e51f20f577e2aab9","datavalue":{"value":{"entity-type":"item","numeric-id":2883865,"id":"Q2883865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$FFC4EC02-6658-4E47-8D3E-3B98064F0B2E","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":"Q2094863$D728292E-A20D-4C50-A24B-A902621C729F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e99da589d7100fee8c775ba840d0a2287dbe7cc7","datavalue":{"value":{"entity-type":"item","numeric-id":4198789,"id":"Q4198789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$DE396029-E4E0-40EF-BCDD-F844A051D357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4d06e8ffe51c0e0e5032701b55a85074de5383c","datavalue":{"value":{"entity-type":"item","numeric-id":5790769,"id":"Q5790769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$96D6F3E6-1351-4D83-BDAA-EA8C08CB3E38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e12ddd3b671c34fe5ef68decec197612fc65b7b6","datavalue":{"value":{"entity-type":"item","numeric-id":1751289,"id":"Q1751289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094863$5045CAD2-68C2-4D2F-A56D-E75A89BF6A23","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"bb30de0242fa7b29414431f5a59742f0f3b4ec0a","datavalue":{"value":"bafkreiafqbiylmtarwfur355pzwhjykv2wy6udqzt4jbyiqg2tenjcysii","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094863$EECB6E52-D0FD-4836-95DA-B7BBD7D01C4F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcf29a1b08420aec0cdfe2157d69519f4ba3d770","datavalue":{"value":{"entity-type":"item","numeric-id":1044923,"id":"Q1044923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3cc4c761ad781a3e66826e9ce7054a37d7d00c4","datavalue":{"value":{"amount":"+0.8439413905143738","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":"Q2094863$B2484C45-11A0-4455-AF1B-B43AB2D3E87B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0d72ebcca2dc62bd0cd1a14193b31beb44a4a66","datavalue":{"value":{"entity-type":"item","numeric-id":2570119,"id":"Q2570119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8041fa94892875486f3ca1dc23c9d61f00d3bd6","datavalue":{"value":{"amount":"+0.8213273286819458","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":"Q2094863$CD1C7C7C-14BB-4A65-B633-2F33C0F8A0E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c4e8fa4e0fe1c737ec8d2fca38e63a4562722a7","datavalue":{"value":{"entity-type":"item","numeric-id":3735724,"id":"Q3735724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6032ae6b5734f478163bd2137f2811230c90c811","datavalue":{"value":{"amount":"+0.8177090883255005","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":"Q2094863$13C992DC-C180-4204-8525-4BDD1F8B5844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1b187ab74213aaf2453faed798cfbea577e47bf","datavalue":{"value":{"entity-type":"item","numeric-id":3480065,"id":"Q3480065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8095c9a919bbae6d838024279dc55b4143c4f45","datavalue":{"value":{"amount":"+0.8120896220207214","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":"Q2094863$DCF97921-3326-4605-AA30-13D21ECA1A32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3ddc8c9f24de6374690f4f4c9b0408601823bca","datavalue":{"value":{"entity-type":"item","numeric-id":630193,"id":"Q630193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e96fd3265bfa303999d09aef9bcc03788f59eb58","datavalue":{"value":{"amount":"+0.8088574409484863","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":"Q2094863$6C54EC1E-8AD5-43A2-AA6D-C2C25C6E0BDA","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":"Q2094863$9375C293-7F15-491D-932A-40E348BC033C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Vizing's and Shannon's theorems for defective edge colouring","badges":[]}}}}}