{"entities":{"Q688209":{"pageid":690058,"ns":120,"title":"Item:Q688209","lastrevid":63490503,"modified":"2026-04-11T13:30:49Z","type":"item","id":"Q688209","labels":{"en":{"language":"en","value":"A comparison of two edge-coloring formulations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 440371"}},"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":"Q688209$190BE42C-187F-4978-ADFB-DD1D2533696A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"46058e6d94f932ae8e8a6f0806e3166e20c1f4c8","datavalue":{"value":{"text":"A comparison of two edge-coloring formulations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q688209$8B06C97B-6820-4595-B53D-95F798D1D2CA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5e265fd7cc12afd3aa22c26ab44a20e812ee5b26","datavalue":{"value":"0783.05049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688209$70CEC481-4C2A-4055-9B49-C1AE52A8A391","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"680b2d0849979bc6aac8443172174158d27fe766","datavalue":{"value":"10.1016/0167-6377(93)90043-G","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688209$DDD9BC47-1B0E-4852-B5DA-6326B6DF54C6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae508c86f07cb97dfaea846bf22fad547f1c58eb","datavalue":{"value":{"entity-type":"item","numeric-id":170438,"id":"Q170438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688209$A072805C-6070-48AA-9395-A06593C649DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"59059677d938071f3bbaf5c97dfe8b6e08bd739f","datavalue":{"value":{"entity-type":"item","numeric-id":1041026,"id":"Q1041026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688209$AB9DEC69-F964-4A14-A7D7-F160C5746584","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688209$DA4AE560-5FCA-4379-971C-466D8B333947","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9a56fa44f05f9c865c2049cda281119f7946a004","datavalue":{"value":{"time":"+1993-11-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":"Q688209$7F7495B5-8373-47A2-ABE1-50DFAD24F137","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"378226ad55aa1888d00afe7b1bff9d2a93dd981b","datavalue":{"value":"Vizing's theorem asserts that the chromatic index \\(\\chi(G)\\) is either \\(\\Delta(G)\\) or \\(\\Delta(G)+1\\), where \\(\\Delta(G)\\) is the maximum degree of a graph \\(G\\). However, determining which of these two alternatives holds is NP-complete. This paper provides a polyhedral formulation for determining \\(\\chi(G)\\), by which it is allowed analytically and computationally to compare to the set-partitioning formulation. Some valid inequalities for this formulation are established.","type":"string"},"datatype":"string"},"type":"statement","id":"Q688209$9729CA05-B4CF-4604-B92D-CA08C55526C2","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":"Q688209$165FB230-89E1-4E83-9516-C1732947F128","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688209$1BB5BF1C-8026-4A3B-BC9C-EA037628C657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688209$429A70BF-BF4C-478C-8212-6C96356C2D15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688209$69449FA3-6FDC-4764-89D5-8C1463D9730D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9bd9cd2a7ce3b00393b117d9b6593e864c045c16","datavalue":{"value":"440371","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688209$DF3AB904-C47D-4BF5-8968-F52861A86D01","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e0a438e9092bcf192a5c493b52b0717e88c2591","datavalue":{"value":"integer programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q688209$CC58C54A-6492-4BE1-8DCB-953471927222","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9995f2ff850ba2e785f2733f4e8a6970ffc49212","datavalue":{"value":"Vizing's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q688209$3ED20A40-978F-4A5F-95CD-31578087A5D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de797320ce0a2184cca07f3061d8f9daa48cc061","datavalue":{"value":"chromatic index","type":"string"},"datatype":"string"},"type":"statement","id":"Q688209$891C2BA4-9ED9-42F6-8AF2-19D1B1BBDEFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13196c9c8a3f396e97e9426bc7763f437026aa4b","datavalue":{"value":"maximum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q688209$6A7B3ABC-EDDF-4491-B0F9-DC9438609134","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q688209$A7DFBA3D-5C08-454D-96BF-C2C9C97EDE7C","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"7c72232bf803200903292e8d91395c8441ec640c","datavalue":{"value":{"entity-type":"item","numeric-id":17125,"id":"Q17125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688209$86E82045-6FBA-4EED-AA62-FFDD3E4B08BD","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":"Q688209$40BB95B8-763F-441D-BF9C-1503356746BA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd8b848f40aaa3f56b8b15df38fbe662aeb1afa","datavalue":{"value":{"entity-type":"item","numeric-id":5516087,"id":"Q5516087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688209$036B5AFB-1C60-4A95-B116-6D1C3301DB73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5335f25c6d6f0cd75a359259eb867be7142f3d9d","datavalue":{"value":{"entity-type":"item","numeric-id":801928,"id":"Q801928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688209$C85B598E-10D3-4628-94CA-6CB4CAD51DDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d1474ad965005531fc787ddda571bd10843eacd","datavalue":{"value":{"entity-type":"item","numeric-id":3853641,"id":"Q3853641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688209$A3012CEA-736C-4565-AEBE-B66FE09C8F39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688209$041DA496-724A-4838-8DEA-74B329A6EA34","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":"Q688209$B41168B4-AF07-41C0-BB2D-51D7891F1A5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0ec4868dba1b37d1adb8bb9f6a23d6c0a862f5","datavalue":{"value":{"entity-type":"item","numeric-id":3880849,"id":"Q3880849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688209$3522C5EC-1ADF-41BD-A1F3-C658C7ADD021","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688209$EE40F73E-92CB-4F22-B8E6-DCFC9996C7FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c1d3332b4ba0eb2671b0eab4a1786d4b21e29f6","datavalue":{"value":{"entity-type":"item","numeric-id":1180838,"id":"Q1180838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688209$C0A5E48B-50FF-490B-A7DB-3BD8E494AD81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fa5c0efe0c39997534bb44636c6730a4e42c655","datavalue":{"value":{"entity-type":"item","numeric-id":3965907,"id":"Q3965907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688209$3B1C3658-B04D-48EB-859E-5511C4CF3425","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":"9d380b1aca54410d33320b3766417c00eead1a5e","datavalue":{"value":{"amount":"+0.8165103793144226","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":"Q688209$BF350A86-80B0-473A-980D-03DF005F9223","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31ce2ede179223f10af00100c2b3d41f8885ef61","datavalue":{"value":{"entity-type":"item","numeric-id":1180838,"id":"Q1180838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c1044dcde83cb4542585d4d440b464721532af6","datavalue":{"value":{"amount":"+0.8106765151023865","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":"Q688209$2B18E410-52EA-497C-8D0C-358A104DECD2","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":"938abf7efdeb25b30ece7b3c7398819b3f94f082","datavalue":{"value":{"amount":"+0.7796293497085571","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":"Q688209$A5EAA153-3587-45D9-9CB7-FDCC8DB35F3D","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":"41d1e7e35ff4678418016153a34f1090ee5998fc","datavalue":{"value":{"amount":"+0.7793997526168823","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":"Q688209$F8EB260B-48E9-4C9F-9D11-883FC8174883","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b443d28d2cf5dc60e84dcdf32fa3ba89e6f4cbe","datavalue":{"value":{"entity-type":"item","numeric-id":4433446,"id":"Q4433446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4842ab4f9f050e7d8567d4892ccaabb4bc5b9d30","datavalue":{"value":{"amount":"+0.7783985733985901","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":"Q688209$E0CAC8C3-D698-4A2C-A1ED-10B0A374200B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A comparison of two edge-coloring formulations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_comparison_of_two_edge-coloring_formulations"}}}}}