{"entities":{"Q2277478":{"pageid":2288221,"ns":120,"title":"Item:Q2277478","lastrevid":49483675,"modified":"2026-01-07T06:09:12Z","type":"item","id":"Q2277478","labels":{"en":{"language":"en","value":"On the fg-coloring of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4195989"}},"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":"Q2277478$55C36BE0-77EB-4284-8C8F-820794EA4A98","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3b3791f14ffe8255a3ac086075b33c8911125e3e","datavalue":{"value":{"text":"On the fg-coloring of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2277478$31DE057B-33BE-464E-9748-50C56B39E139","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c5dfdeddf2c9115f1e09c61b1766e08d4a2c855a","datavalue":{"value":"0725.05040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277478$8D7697D9-03B1-4E58-A3E4-5432118F8DC2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7a3bbf472caaedcd8c0ae0a49a19635a5d7c50af","datavalue":{"value":"10.1007/BF02122697","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277478$B7043178-042A-4587-8C97-CDE890CB470D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d644e433a66335990abf68d3b7d722a950cb6450","datavalue":{"value":{"entity-type":"item","numeric-id":238445,"id":"Q238445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277478$CDBFF6BF-5BE3-4E37-BD2E-7A55D7138D08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"da93d7c45d552338138e673e141df03679ac5cb5","datavalue":{"value":{"entity-type":"item","numeric-id":226821,"id":"Q226821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277478$2E382646-7302-44E7-9D05-DB45E696B33C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6d6129f2694707a8dc943ba2b6db8331eade716e","datavalue":{"value":{"entity-type":"item","numeric-id":788488,"id":"Q788488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277478$0BD31D53-C3BA-49BC-B761-E45B354DA28D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277478$784F1043-7473-492D-958D-67B8463CFE54","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q2277478$9A046050-68CB-4C51-B8F1-82B58EC4B4F5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"be92de8beba723b1c66ece332a3342b7ad53b74d","datavalue":{"value":"In this paper multigraphs \\(G=(V,E)\\) without loops are under consideration. They are assigned edge colourings satisfying the following two conditions:    (i) Each colour appears at each vertex v no more than f(v) times.    (ii) Each colour appears at each set of multiple edges joining vertices v and w no more than g(vw) times.    These edge colourings are called fg-colourings. \\(q^*_{fg}(G)\\) denotes the minimum number of colours needed to fg-colour a multigraph G. Various upper bounds on \\(g^*_{fg}(G)\\) are given. The main result is  \\[  q^*_{fg}(G)\\leq \\max_{vw\\in G}\\lceil d(v)/f(v)+p(vw)/g(vw)\\rceil.  \\]  A polynomial time algorithm to fg-colour a given multigraph using \\(\\leq 2q^*_{fg}(G)\\) colours is presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277478$38794FD1-4DCB-45D5-842C-965A1DE659AD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277478$A4C36B64-C315-459D-8C1D-4E6A3C579D1F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d81e7bda81dd46421dd889129eb9471f1bcd265","datavalue":{"value":"4195989","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277478$DA1812FA-7BBD-467B-AE8F-FC4B560F0BFE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"010b411e0c821bf2c612857bdb20a91f3a0f34d0","datavalue":{"value":"fg-chromatic index","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277478$B9FB916F-1B53-4235-BE11-5E7AB1256843","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae7d78c9d50113c81c33dea1ce63525cb023ef40","datavalue":{"value":"multigraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277478$6EE764BD-5D9C-4829-918C-CEB987912E40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a8bbe8ce40df8dbd600f83b7e72b38f56a1ae57","datavalue":{"value":"edge colourings","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277478$B13CC9C3-5D06-4395-BB1C-5EE7FDC6CF09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1574899a16d3945c938d3e4fad62a91e7d55050f","datavalue":{"value":"fg-colourings","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277478$67171CE8-A08E-4AA8-8CAF-2E5AE56C22D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277478$367A39B7-A1FC-49D2-ACAB-51BC12802B69","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e82f32c91e1eb0067a512f27a8cb077a4f29f958","datavalue":{"value":{"entity-type":"item","numeric-id":640843,"id":"Q640843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277478$C9168C96-F211-4702-8139-1E7D2F2947E2","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":"Q2277478$5ED24B52-232C-407F-B487-66AB0078E4FC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277478$1232C62E-75EE-493F-BE33-A76B4BDA1F44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fae306fb5b216ca7a979cf42513dbb739d5ef6cf","datavalue":{"value":{"entity-type":"item","numeric-id":3741046,"id":"Q3741046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277478$26C4EFCD-F99B-4273-8AE5-334FBB5610EB","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":"Q2277478$C28D2018-0942-4ED9-BA46-4402D1803E6B","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":"Q2277478$B25BCB5F-A95A-4DE7-82FE-579FC5C4D2A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"583c931d5792f7839319cb6b458bd9d7cd7cc3b3","datavalue":{"value":{"entity-type":"item","numeric-id":3735724,"id":"Q3735724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277478$B6985756-11E9-4517-A86E-20D1481DC741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59b99f23c21d3771a98a9f9662331f20e4d3e99c","datavalue":{"value":{"entity-type":"item","numeric-id":3725544,"id":"Q3725544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277478$90158A21-1D2F-43FE-9357-7B5E27B96670","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":"Q2277478$D0910578-989A-45B9-8340-21E426C022FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b80bb422f9ba021021a7389f33a7599d4c9d9dc4","datavalue":{"value":{"entity-type":"item","numeric-id":3778781,"id":"Q3778781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277478$157F457A-CDF2-4527-A4EC-41411F2F1A33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8aa987004d05e3c76349ea782163761aea7b4d6c","datavalue":{"value":{"entity-type":"item","numeric-id":3693539,"id":"Q3693539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277478$E29D3575-EDFD-4271-8CF4-FE61A4006618","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":"Q2277478$D17C7E06-1A75-4582-82D9-B1F7F212A89F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e459611a95efb8cad8fe88c54e914d9dc03cd596","datavalue":{"value":{"entity-type":"item","numeric-id":4517442,"id":"Q4517442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277478$6DF60D53-2F1A-4333-A512-5D82E6C21E9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c83bcd87fc99f332c71e38d515e1a4b8318e297","datavalue":{"value":{"entity-type":"item","numeric-id":4052161,"id":"Q4052161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277478$5711E621-0AEC-47DF-B1A7-0D780BCE7D70","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c1b9a0ac087b14b21ad24cd7a6127f937cce4916","datavalue":{"value":"https://doi.org/10.1007/bf02122697","type":"string"},"datatype":"url"},"type":"statement","id":"Q2277478$1170B3C4-7C82-40EC-9775-57728DF1B50B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"23c94447dd803ab80e96d741005629b1ffa09602","datavalue":{"value":"W1486913849","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277478$BB527953-BF8E-44A1-A8AC-166ECEA09AD7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88811b57848fbf6eb3c090cd8675508354197d22","datavalue":{"value":{"entity-type":"item","numeric-id":3778781,"id":"Q3778781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f556cf45d0935e69d9a362975b9be79882549dd9","datavalue":{"value":{"amount":"+0.8958621025085449","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":"Q2277478$E3F32039-8E61-4C39-896B-E9B3AC9B82AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9de46c846329dc7628483b8d9bbef81b34ffce5d","datavalue":{"value":{"entity-type":"item","numeric-id":4243441,"id":"Q4243441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9dbdf3f789fd121e28d4ca52474b0e4293a6213","datavalue":{"value":{"amount":"+0.828137993812561","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":"Q2277478$2A40FC32-BC7F-44BC-9FD6-4680C67722CD","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":"b72929ed9a069a3c4c1516aa0c8995358fa25500","datavalue":{"value":{"amount":"+0.8269761204719543","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":"Q2277478$18430363-D53E-445D-AF42-1E2603865735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6d7173d2126a398ca920893e0dc2d81e0914614","datavalue":{"value":{"entity-type":"item","numeric-id":3052514,"id":"Q3052514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a33ad1956e2ec7b2f9c714676067d5c4fc0304a4","datavalue":{"value":{"amount":"+0.8258804678916931","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":"Q2277478$7BBA565D-9EA8-4E84-ACF4-52F9F2249094","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94451e235c1f384cdc91cd2b3d55c5fe0ff0fd37","datavalue":{"value":{"entity-type":"item","numeric-id":4525701,"id":"Q4525701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10506216ca995ae42904a09f5d1c3a18be7c7566","datavalue":{"value":{"amount":"+0.824302077293396","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":"Q2277478$04782EC7-9838-4561-B414-1D173BC2C648","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2277478","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2277478"}}}}}