{"entities":{"Q1884769":{"pageid":1895511,"ns":120,"title":"Item:Q1884769","lastrevid":73703982,"modified":"2026-04-14T16:58:32Z","type":"item","id":"Q1884769","labels":{"en":{"language":"en","value":"Sum coloring of bipartite graphs with bounded degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2113911"}},"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":"Q1884769$5EA53A3C-4632-4DCD-AC14-EF7E5952A997","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a48cb663b8fa8c5ee9fb19ebf7038420095c36ad","datavalue":{"value":{"text":"Sum coloring of bipartite graphs with bounded degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1884769$74F665DD-F14B-4D0C-976D-10585C030B1C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9ee7f103084c54414ce7f995d3d3415dde26c666","datavalue":{"value":"1084.05029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884769$3B2947E2-323C-4BB5-8E44-9CE556648AFD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"681fa36f324bfdb5f85fc6878945cb77d35a0028","datavalue":{"value":{"entity-type":"item","numeric-id":237430,"id":"Q237430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1884769$F17AB604-0670-4B89-976D-12343B9DA201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"df859106777b262ea1e16ccf8d0885099b524191","datavalue":{"value":{"entity-type":"item","numeric-id":177037,"id":"Q177037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1884769$66EE2E64-C2E8-41C2-BEEF-B9A111EED9DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6e77dc62432e0084fdda4e3c056dc8f26060354d","datavalue":{"value":{"entity-type":"item","numeric-id":186209,"id":"Q186209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1884769$EAAC2941-2B47-4D79-8306-B0796F91B205","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2681750faeff29d5132b89d9392ae6736d25c7cd","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1884769$E87F5599-B9C4-444E-8750-75349965754E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1884769$AB828D9C-0224-4243-BEA2-61E354A94996","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"66f51029b9e38c366fbfa63f3a7b20beee0c294d","datavalue":{"value":{"time":"+2004-11-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1884769$DBAD754C-993A-405D-8C5B-824783AF3235","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a4fa07d7d706f0d0c8fa36ce68a638e346c977d5","datavalue":{"value":"A coloring of a graph \\(G=(V, E)\\) is a function \\(c: V \\rightarrow \\mathbb N\\) such that, for all adjacent vertices \\( v\\) and \\(w\\), \\(c(v)\\not= c(w)\\). Given a graph \\(G=(V, E)\\) and a positive integer \\(k\\), the chromatic sum problem (CSP) asks whether or not \\(\\min\\sum_{v\\in V} c(v)\\leq k\\), where the minimum is taken over all colorings \\(c\\) of \\(G\\). The sum coloring problem (SCP) asks for a (best) coloring \\(c\\) with minimum sum \\(\\sum_{v\\in V} c(v)\\).   The authors prove that CSP is NP-complete on planar bipartite graphs with maximum degree \\(\\leq 5\\), and can be soved in \\(O(| V| ^2)\\) time on bipartite graphs of maximum degree \\(\\leq 3\\). The authors conjecture that CSP is polynomial solvable on bipartite graphs with maximum degree \\(\\leq 4\\). They also give a \\(27/26\\)-approximation algorithm for SCP on bipartite graphs, improving a result proved by \\textit{A. Bar-Noy} and \\textit{G. Kortsarz} [J. Algorithms 28, 339-365 (1998; Zbl 0936.68076)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1884769$BE236B67-86B2-402B-8DBD-CC301447C4A0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c4d08f81dccf0def423a8aaa09abdd52c85c61ef","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1884769$3C221660-129D-48DF-9896-5B8BF48020B9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884769$751971B8-043A-4108-90ED-1C17A7A09D0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884769$E0F42582-2CBA-4CA1-BC10-7DEADB7B297D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"45016c6933d070b73ccd1325a3ca4c2b4b8cee8b","datavalue":{"value":"2113911","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884769$89E45530-860D-4634-BFDE-91E195A211D5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15b66a6079b846629b0c8e49fc4dd12461f6a73e","datavalue":{"value":"chromatic sum","type":"string"},"datatype":"string"},"type":"statement","id":"Q1884769$4FD27CF4-DE2D-4E77-A348-526803507FA2","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":"Q1884769$1ACBBE88-0F03-4902-91A1-F5CF2A658E6D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7c575096f0666661c3f0c2f50960257e127c647d","datavalue":{"value":"https://doi.org/10.1007/s00453-004-1111-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1884769$DAF90EAB-93CB-48AD-85E0-9318A65D4FE0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4c2de50ac162b73a42186d7243df1a62e882cff1","datavalue":{"value":"W2095158197","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884769$B8872BA1-B633-4EF4-B5B4-BA5748DBBA87","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"79ea0be0a56c4c350e7a56d275bd19ad16b1c4cf","datavalue":{"value":"10.1007/S00453-004-1111-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1884769$DD0C2570-A072-4E2C-8DEB-AE33271F3ECD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abf9c051e334959a8fb21512edb4af947ce3273c","datavalue":{"value":{"entity-type":"item","numeric-id":4572002,"id":"Q4572002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c93f9b011795076c5dff4f5ebed0d4ea0e774007","datavalue":{"value":{"amount":"+0.93096393","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884769$F2B569DA-45D2-435E-A074-9AB948875DD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"864e64c3f94d96d807cef8729051a2a704db617e","datavalue":{"value":{"entity-type":"item","numeric-id":4209269,"id":"Q4209269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7178e2800f8d784ea9af890a74974e5910c254d6","datavalue":{"value":{"amount":"+0.92542183","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884769$1FC4F0B2-0BED-4D1F-AB49-1BAAE46910A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f010cfbcff665c7ea133dd121d113b88ac19c98","datavalue":{"value":{"entity-type":"item","numeric-id":2448910,"id":"Q2448910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a4393d3a9fb419a800e2940658af6a21bd5e3b6","datavalue":{"value":{"amount":"+0.92413616","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884769$42DC9392-4BD0-4E36-8651-B173A7457109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65b8e4c502161de05670b0766d4b8b42c1288751","datavalue":{"value":{"entity-type":"item","numeric-id":1811069,"id":"Q1811069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e941e5b5582c4e641f75047aa0f40d98cf1e89b6","datavalue":{"value":{"amount":"+0.92305624","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884769$747DFFCC-BFD0-4D8D-8D22-17E075ED5BEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e684ac82a4b2c120816701a180f0ead7880009d7","datavalue":{"value":{"entity-type":"item","numeric-id":5488889,"id":"Q5488889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef054a989c847367a5f60f04b3dbb02e1bb15d61","datavalue":{"value":{"amount":"+0.9208605","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884769$E13EE238-F8FF-4A63-A7E6-7C36B93FBAD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66d0909063ead11bedd59244e3404e322ebb5b64","datavalue":{"value":{"entity-type":"item","numeric-id":2906843,"id":"Q2906843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"272c53ae4ad68ea5e1d0bfe2a9042e2a8fbbfa3c","datavalue":{"value":{"amount":"+0.9203295","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884769$AE9E4601-050F-4332-99CC-B05A9BB005A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1bb1eeec569d8c4cf82d0f0cb1849c76dd65685","datavalue":{"value":{"entity-type":"item","numeric-id":2403698,"id":"Q2403698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68c4c76e51288b7845a9624edeaa96f2a7a3386b","datavalue":{"value":{"amount":"+0.915932","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884769$EC3B1F69-025F-42D5-A192-607D7C0A4FBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"285f6c254d882abb47e9007907fbc48d1da37449","datavalue":{"value":{"entity-type":"item","numeric-id":4559904,"id":"Q4559904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dff8f277c532239a1fbeb510b40a3786788c403f","datavalue":{"value":{"amount":"+0.91464216","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884769$E458EDF6-4DF0-414F-BB56-AF562D2DC5C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ed83738639d54167e17242d624fa4a24ed28d8a","datavalue":{"value":{"entity-type":"item","numeric-id":2184694,"id":"Q2184694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1337abd16f91d050a411dde9e5184d541a797e0","datavalue":{"value":{"amount":"+0.9112338","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884769$290764F6-6A30-4E44-A690-B1D8246041E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b6d002c316cebf51433242ba1cb936afe7aba38","datavalue":{"value":{"entity-type":"item","numeric-id":967294,"id":"Q967294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d2cae9997a0dd09290aec08999db8279a3480b5","datavalue":{"value":{"amount":"+0.9091831","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1884769$BC6FF52E-789A-465D-8321-B1FC308BA333","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Sum coloring of bipartite graphs with bounded degree","badges":[]}}}}}