{"entities":{"Q6928025":{"pageid":21071341,"ns":120,"title":"Item:Q6928025","lastrevid":84127406,"modified":"2026-05-10T18:08:39Z","type":"item","id":"Q6928025","labels":{"en":{"language":"en","value":"The proper conflict-free \\(k\\)-coloring problem and the odd \\(k\\)-coloring problem are NP-complete on bipartite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8095531"}},"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":"Q6928025$F79C7F09-08CE-43E9-A2C9-1389D6156125","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7fe798500d29bfde2c4ec92dff65236c46575ebe","datavalue":{"value":{"text":"The proper conflict-free \\(k\\)-coloring problem and the odd \\(k\\)-coloring problem are NP-complete on bipartite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6928025$005B196E-8F63-42F1-9F23-EC351D77FC91","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6b302da16676526c40e9f6b1d125f20178757579","datavalue":{"value":"1572.05073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6928025$0334CF2E-607B-4E9C-B10F-B76792FF2961","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f5475729c4da29a2ae1054ff793f5d4afa3ada10","datavalue":{"value":"10.1016/J.DAM.2025.06.026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6928025$A39C18B9-6660-459E-9933-63FF1AF5EC82","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8110ca7c7298352bf02fda6c8be0216ac5acad5e","datavalue":{"value":{"entity-type":"item","numeric-id":2110615,"id":"Q2110615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$EB7A1180-A707-4606-9BD3-6B0B41448CD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e0b58bcc0d27d80e5baff6b64d069c7a3045cc27","datavalue":{"value":{"entity-type":"item","numeric-id":499466,"id":"Q499466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$F28A430C-BA5C-45F9-BB5A-786AA677C6FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6c9c8d991cb59f8bfb573d1c78b1770eda9953fc","datavalue":{"value":{"entity-type":"item","numeric-id":256976,"id":"Q256976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$A42DAB89-8D3E-4DB5-BF15-BACF31A86909","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$DA8D6979-1FDC-452E-B824-D3E63DB5EEB9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"647ca4e88a384c5bf6e89a2b31c50839848248aa","datavalue":{"value":{"time":"+2025-09-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6928025$0B0A97D6-15D0-4E83-9D9F-1768DA12FC89","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6928025$51997300-4B48-4AAA-ABDF-DC9E457080AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6928025$BB90DDF6-923F-446B-ADE7-64AA90FD9BE7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a705b02e823212cb0b455f23456d9c1d25cc7348","datavalue":{"value":"8095531","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6928025$F30B2E4B-7DFE-4535-9811-4AD701FB7CB2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a11c1c9dfaab12ff9f9f233f6a1c8251abcd8d90","datavalue":{"value":"proper conflict-free coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6928025$1A4F3369-E9AB-4B02-BE7F-2F0F31F6F231","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4642cb5f59a32d20bfc2644c3a979efeb720884f","datavalue":{"value":"odd coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6928025$929AC9CA-02C8-47A0-A12D-585CF5D9F2E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6928025$BE2C2C4A-9253-41ED-BFC1-79C95574C2D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6928025$403F5E3D-32CD-4DDA-AF0F-95FA5E6010AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q6928025$206B84FF-0BBA-4034-9BAD-2697DA67E383","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":"Q6928025$CA0B845E-E9D4-4B71-A8C7-F8390C1BA1E7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"225c92174e7c29eb9eb744cd47b5ceaba94b8219","datavalue":{"value":{"entity-type":"item","numeric-id":2172423,"id":"Q2172423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$3937627D-82EF-49A4-AB20-80047347C0BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de6d098e6e060c91e86b0fb487a155d12900de76","datavalue":{"value":{"entity-type":"item","numeric-id":2099465,"id":"Q2099465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$41723D4B-3584-4370-B436-154950E2D057","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80e71ba0388ab9b5752ca5621034411695fbcae1","datavalue":{"value":{"entity-type":"item","numeric-id":2689480,"id":"Q2689480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$85F3DE7D-EC61-4CFB-A92B-6717B74C5E79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34f21b2fc3c5d8cb508d3fe6c90c5a7085b39a87","datavalue":{"value":{"entity-type":"item","numeric-id":6657259,"id":"Q6657259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$29BD1933-41D9-4E0D-BFAD-5514DD680E85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aff5612c16dd14373cb0f87412e3b762b530d55b","datavalue":{"value":{"entity-type":"item","numeric-id":858683,"id":"Q858683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$E24A7E94-6835-4FFA-A2D4-BAD0CE846953","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b37593c77aa82eea9e38b64c6f2f378abdd0ddb","datavalue":{"value":{"entity-type":"item","numeric-id":6641735,"id":"Q6641735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$07C1AABB-927C-47A9-99DF-9899E90ED934","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b74c3b11c2caacd0c9a58c0de91e6efab6e4c8d1","datavalue":{"value":{"entity-type":"item","numeric-id":2689651,"id":"Q2689651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$AC01E32A-ADB1-4DFB-982C-F5A58A2C3472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58b61035aba80080d8bbf3e4f2d6d53c41bd8ecf","datavalue":{"value":{"entity-type":"item","numeric-id":6613246,"id":"Q6613246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$327E7BB7-5729-4436-A0AD-B9310BCD217B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65f2208a858e6457313387dc4c136c11b54bbb30","datavalue":{"value":{"entity-type":"item","numeric-id":2097169,"id":"Q2097169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$0CAE9EB8-0EED-4C53-8A19-9873576C043B","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":"Q6928025$3845E27E-7403-4973-812B-D51FCC628482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c47ae613a1176cff4c9ef1f3b13c76ce994629df","datavalue":{"value":{"entity-type":"item","numeric-id":6072045,"id":"Q6072045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$2B96C395-049C-4643-8D8F-36F1F675DBCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4654aae8b18d38dae6f3ee82111d1335fc96fe89","datavalue":{"value":{"entity-type":"item","numeric-id":5932643,"id":"Q5932643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$59D200FB-5129-4AF1-9F54-22904CF98943","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3c4a86d76c42f34ea26a0ac7aaf144adbff3c67","datavalue":{"value":{"entity-type":"item","numeric-id":1003864,"id":"Q1003864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$181F7F71-3B78-45F2-8398-CAF1C92921E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba21be70b6da1827f3b768889353ed94facd00bd","datavalue":{"value":{"entity-type":"item","numeric-id":6080127,"id":"Q6080127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$2140232D-A8AA-47A7-8D69-2F382A367A8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9964596a6f263ed464de439f5347d02890494490","datavalue":{"value":{"entity-type":"item","numeric-id":2172422,"id":"Q2172422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$D3A990C4-6C2C-441C-B307-4388C99C5EC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c5b0f19170beb2785093633ac27641fb2c3d131","datavalue":{"value":{"entity-type":"item","numeric-id":6081577,"id":"Q6081577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6928025$0EC52905-E65A-44DD-91C5-4AE947D1BFA0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The proper conflict-free \\(k\\)-coloring problem and the odd \\(k\\)-coloring problem are NP-complete on bipartite graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_proper_conflict-free_%5C(k%5C)-coloring_problem_and_the_odd_%5C(k%5C)-coloring_problem_are_NP-complete_on_bipartite_graphs"}}}}}