{"entities":{"Q1579549":{"pageid":1590289,"ns":120,"title":"Item:Q1579549","lastrevid":72241332,"modified":"2026-04-14T03:34:58Z","type":"item","id":"Q1579549","labels":{"en":{"language":"en","value":"Feasible edge colorings of trees with cardinality constraints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1506818"}},"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":"Q1579549$2E7B10A8-C114-469F-B6E6-3BFCDFD70642","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4341e89fd88424fd9bc66c08bfe7a9e823d5d231","datavalue":{"value":{"text":"Feasible edge colorings of trees with cardinality constraints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1579549$7A09AD31-91E5-4AB1-B6C4-A1754E4CBCF9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a673b77995009b50f5277199f925e60345f94ec9","datavalue":{"value":"0963.05057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579549$E342E7D1-6DB8-45DF-9F6E-E1042BF2B573","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8849bc95609b8e7c13323a827e9de6b88dc12fc6","datavalue":{"value":"10.1016/S0012-365X(00)00006-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579549$489F458F-5BBF-482F-B132-A85F3008ED65","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"982f5091aa6783300b33c5810a51dbd1cdf0e96b","datavalue":{"value":{"entity-type":"item","numeric-id":686489,"id":"Q686489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579549$2DC2D32C-10BE-4A6E-841F-BDA17A1FAE8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"467bce3dcf8136ea7a4832a7c85d350a56e9a245","datavalue":{"value":{"entity-type":"item","numeric-id":224825,"id":"Q224825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579549$785A3CF2-AEA4-4D54-B6D0-AA216EDBE99A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4249c9a7a0b14df0599e70315ca2a040457d857c","datavalue":{"value":{"entity-type":"item","numeric-id":260023,"id":"Q260023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579549$4071354A-D1AA-477E-A928-82831A076C04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"61f96647728e8d9cf38c91c3045ddf65bddf2136","datavalue":{"value":{"entity-type":"item","numeric-id":183294,"id":"Q183294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579549$1A07A55F-47B9-4496-8EA0-A1D5E42B75B4","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":"Q1579549$82F086A0-FE48-411B-82D0-FFDEB4EF6B9C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cb40d11281955feb9c83549c13a27c60db3daa79","datavalue":{"value":{"time":"+2001-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":"Q1579549$399F01FF-18A8-4B9E-B8D1-3D17106030BD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"31d083d40dccc25275e5f778bfbb49265816c3f8","datavalue":{"value":"The following two extensions of the well-known regular edge colouring are considered. The first imposes cardinality constraints by fixing the number of times each colour can be used and the second restricts the set of possible colours that each edge can receive. The authors prove that both extensions are polynomially solvable for trees with maximum degree bounded by a constant. It is known that determining whether a given graph has an edge colouring satisfying the above constraints is a NP-complete problem, even if restricted to general bipartite multigraphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579549$D21F664C-BBA3-41D0-AF7C-1AAC37BFE536","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"fa01ee8d01fdc058743d4cb5961413365b30dd30","datavalue":{"value":{"entity-type":"item","numeric-id":587976,"id":"Q587976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579549$DAC54EFD-1D24-4236-B8BB-CB219D6C5269","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579549$ED0AD5CE-611B-47EB-8C70-21C07A25C9E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579549$2AA1EEFC-B7DE-409E-83CF-396FE05EA060","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5cc625a24c4e5a0242b3314bfc4ca12d3fad1fc4","datavalue":{"value":"1506818","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579549$78D9266E-1733-40C4-B8AF-4656170A96B3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dd8eded4c3e41e4de8044cb30928abf4579fa27","datavalue":{"value":"cost","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579549$53F59CDC-ADBE-4A2A-BD6B-26D86263BECB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25fa47f9463d515b352593e567b1400b4df9f27b","datavalue":{"value":"timetabling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579549$BE0AF779-EB29-4C3A-A97B-71FC2358FD63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e3d58b5f68ae7d6337620e7d25da0081273ed23","datavalue":{"value":"edge colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579549$ADE18B0B-6F0A-40A4-B7BD-6D052D5A58DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"55f22188f120daab160d89caf625f27e583414e1","datavalue":{"value":"cardinality constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579549$D29BA271-40D6-4791-9029-88C1A2028DF5","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":"Q1579549$A9D5B024-C409-4B30-8A63-2092F0B739F6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7db3971a1177c35f15cd93a2dd89bda5c019c383","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00006-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1579549$652BA7C1-A3C5-4EBB-94DF-C18F9569EFAB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a77112cd8fd977aa2d5bb8f65253d1f700614862","datavalue":{"value":"W2062819334","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579549$3C1FA2CA-01DB-4343-AB18-7552C562EC7C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc949b6a9bc3bff3fd86b1ea5c83eb5332a4ae25","datavalue":{"value":{"entity-type":"item","numeric-id":5026976,"id":"Q5026976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4349c988a3a17b02f36a0e6122b916ca6552acc1","datavalue":{"value":{"amount":"+0.8026946783065796","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":"Q1579549$6A218CF8-0AF4-4203-A5BA-65F76DFF1ACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"438639c88273a8ad0c7cb4c6ffb4aad472646577","datavalue":{"value":{"entity-type":"item","numeric-id":1040081,"id":"Q1040081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9572c0a7b8188bec040167a1b23f9011233b2100","datavalue":{"value":{"amount":"+0.7915429472923279","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":"Q1579549$07A5C791-9BAD-48C8-BE28-D1E9558912F1","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":"6f268520fda5444d172e6e6c790ec9411e636f7f","datavalue":{"value":{"amount":"+0.7850531339645386","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":"Q1579549$D7F8723F-69F0-468A-8B74-A92EDF9478D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c78c68fdb8e9aeaafc49d2d3c8d506168af2d081","datavalue":{"value":{"entity-type":"item","numeric-id":5100181,"id":"Q5100181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8b3321bc789b106d461b80a29549c326443aa87","datavalue":{"value":{"amount":"+0.7847449779510498","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":"Q1579549$2EE9D6D0-0A5D-44BB-BC2E-A14925C11D96","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":"0b0be136213d2ed636f1ffef15a1be0fd6950596","datavalue":{"value":{"amount":"+0.7799237966537476","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":"Q1579549$124C08A3-A48E-4660-9BCD-3C1072B8956E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Feasible edge colorings of trees with cardinality constraints","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Feasible_edge_colorings_of_trees_with_cardinality_constraints"}}}}}