{"entities":{"Q1336741":{"pageid":1347480,"ns":120,"title":"Item:Q1336741","lastrevid":43039685,"modified":"2025-07-17T03:40:33Z","type":"item","id":"Q1336741","labels":{"en":{"language":"en","value":"Maximizing the number of unused colors in the vertex coloring problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 681758"}},"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":"Q1336741$2730BBCE-6DE6-4B8C-B22F-A69BEA3079E5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0c579d8ade591b37c8e86be2785859fb5944dc5a","datavalue":{"value":{"text":"Maximizing the number of unused colors in the vertex coloring problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1336741$2DCC6C81-F279-4FA9-8A49-DE5BC746DA6C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f3c35f5a3e5c1e68cccee599fd0ec3d1df997e9b","datavalue":{"value":"0809.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336741$2EA53F0D-815F-4197-82BE-304C3C7CECD3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fe3d0c110218c53155ebc199b2feb5cc249eeefb","datavalue":{"value":"10.1016/0020-0190(94)00113-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336741$8B73CFB7-FC33-4D39-B406-35B4301FAEFF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3652c12d936f991ecdd7c90b239b5e20fe061f51","datavalue":{"value":{"entity-type":"item","numeric-id":1336740,"id":"Q1336740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336741$5917BD5A-5671-4209-B5C4-10046D829A40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f54f6d518946c4faa452b02158d231b7ca863f0c","datavalue":{"value":{"entity-type":"item","numeric-id":233539,"id":"Q233539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336741$F9676A3C-7DE8-40C7-9BF3-1C68BBE3A6E4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336741$66EE32DB-2F02-4A50-9BE0-14174287DA25","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1f45624994ac2bf1f53d8535bc357de536b6c637","datavalue":{"value":{"time":"+1994-12-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1336741$6B8BC87D-67E9-4475-BC86-FE5573ADB202","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8d5e28470e31420b96ec36ce650a05466c0e6ac6","datavalue":{"value":"For a graph \\(G\\) if \\(| V(G)|\\) colors are available, a coloring of the vertices of \\(G\\) is always possible. However, for a given noncomplete graph, usually not all of these colors are necessary and the problem considered in this paper is that of maximizing the number of unused colors.   An algorithm yielding a coloring of \\(G\\) of order \\(n\\) is proposed such that each color class contains at most three vertices and if \\(\\chi\\) and \\(\\chi'\\) denote the size of a coloring of minimum size and the size of the coloring produced by this algorithm, respectively, one has \\(n- \\chi'\\geq {2\\over 3} (n-\\chi)\\), and the bound is tight.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336741$A023DC89-8749-44E3-9BD4-AE6DBF7BE1A8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336741$6A7B6DC5-DC90-4E19-900C-E6343B68441E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336741$F24C1E65-683E-4F07-B82C-F725C6C8DD76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336741$164CD601-9E61-4D04-BA34-382BC9A5A3F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336741$5F80F048-7786-4B97-8461-0A3CFFB91046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336741$71674E59-2965-454A-A89F-258375EA5754","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c9542eaf6349e5ffe10add52ceb4c6c4fc6cde54","datavalue":{"value":"681758","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336741$7173EA6A-EE9D-4064-9060-B530D37A94F0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85dfdbd7a975d6137b355769addaba184ea21dc4","datavalue":{"value":"vertex coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336741$CFC27F2E-396A-4B6A-97E2-237D946F3CF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56922b44f4b77c888d5a91237cc4964d535123f5","datavalue":{"value":"matching problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336741$06162904-3FD3-4CBB-B292-4F2AD06F355E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d18c6b1ea0df055126b0681611c13c8749505af","datavalue":{"value":"unused colors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336741$C596EE02-D1D3-47EC-87E9-085C8C9026A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336741$06783236-3DCC-41A5-A390-B29725A6980C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4717a41954416e781c8ad802af029055a339399d","datavalue":{"value":"color class","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336741$71284B37-961F-4BD7-B8C8-52B8E6BBCB05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6906d309434fd0c76118d23a6a15594e9c5ca39","datavalue":{"value":"bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1336741$31862E97-51B1-4BF5-8C3B-865FB03175E7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336741$AF4731F3-E22A-45DA-9741-E78BEE3CE13E","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":"Q1336741$F2FC71C8-26E6-4852-9BB0-AB22DED39F3A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"97566b6eb7dad5e07417290d8aa90de3baaae114","datavalue":{"value":"https://doi.org/10.1016/0020-0190(94)00113-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1336741$5CFD1542-C5B0-4D86-AF3F-97A938957BA2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f12099b79b6f042e3b221501656fd2f259d30a6b","datavalue":{"value":"W2095314925","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1336741$8C9EC972-561B-433D-AEE7-62D0A6FDC412","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"614ec8e56e53193dd4d76b8123652b8af4b40489","datavalue":{"value":{"entity-type":"item","numeric-id":1321829,"id":"Q1321829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336741$7735375B-545B-424C-AA70-4A28A4D2A085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336741$ED20118D-47FE-4359-9E5B-C83F9FACA9BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d8549af636d2abe2c2be6c22ae2647ebb36e4d3","datavalue":{"value":{"entity-type":"item","numeric-id":5248497,"id":"Q5248497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1336741$A4C46778-82D4-4626-B976-5170FCAE54A1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7154f57bd914dd079721030902d048168e7a8763","datavalue":{"value":{"entity-type":"item","numeric-id":490999,"id":"Q490999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59eac6243eb8d129a1473f7b89915e9cc750aca0","datavalue":{"value":{"amount":"+0.8981858","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":"Q1336741$26096900-9008-445C-82E7-5D955C2AC87D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f817adb5be5cc51da6197c385ffec08ef4016983","datavalue":{"value":{"entity-type":"item","numeric-id":5964985,"id":"Q5964985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d43013802ab0d57b0fe0a7f70865d1febf23b00f","datavalue":{"value":{"amount":"+0.8939039","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":"Q1336741$D95D0FB0-9B44-4ADA-B535-6DCCCF732AC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7be40bdfb0e30f9aff7116ecc381f3c1bfd9388","datavalue":{"value":{"entity-type":"item","numeric-id":690449,"id":"Q690449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7cc35b818ea96bec79261b2afca7be73dcfa535","datavalue":{"value":{"amount":"+0.88814175","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":"Q1336741$F53136C6-A475-4F66-A820-EDCDCA017904","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fd70b380235274b420096bbf4d243e1c3c37a59","datavalue":{"value":{"entity-type":"item","numeric-id":5443379,"id":"Q5443379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75350db637e2c049d1c10603cafd11c64da3a752","datavalue":{"value":{"amount":"+0.8881417","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":"Q1336741$86DFB047-46AD-4E22-833A-EF39E4C4772F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"296650fd255de4bc818c78ae08ecb8d9b2ffe2fa","datavalue":{"value":{"entity-type":"item","numeric-id":5241611,"id":"Q5241611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b30f769eac10dcf53beb78c89c05c0920c3e5c0","datavalue":{"value":{"amount":"+0.88563967","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":"Q1336741$DCF16E45-C131-47FB-B0CA-DA118A414805","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c9473b0f92159d642cbed27add91082c19dade9","datavalue":{"value":{"entity-type":"item","numeric-id":1791008,"id":"Q1791008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05340d18fbd87e25f2d413975f7654cee41d2ec4","datavalue":{"value":{"amount":"+0.88385975","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":"Q1336741$613FF236-86D3-4414-A457-C989884BC312","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f8d78171a699fb3b4b68294926db1185544b9da","datavalue":{"value":{"entity-type":"item","numeric-id":1625149,"id":"Q1625149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4592949c33beb8985728b666851d97bad9a07c7","datavalue":{"value":{"amount":"+0.8833578","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":"Q1336741$6C78EFAA-100E-467F-BDE4-1BEC71771098","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cecaf4e385606fac6d9517d038315b326eb0459","datavalue":{"value":{"entity-type":"item","numeric-id":3059717,"id":"Q3059717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c05d200e26282ed630bfc515ca2cd0b307a14332","datavalue":{"value":{"amount":"+0.88279194","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":"Q1336741$12BA6D5B-0A93-4582-8372-2D1DEED4F57C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f0b97a2be52f3f431f7eb5ef6713fea93e52f98","datavalue":{"value":{"entity-type":"item","numeric-id":408951,"id":"Q408951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6fa705847f01a01f71acb617df14f7bd05a1ece","datavalue":{"value":{"amount":"+0.8810975","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":"Q1336741$38D76048-3BDB-4980-BCF1-26AEF3CD25E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85339ba724835ba27aa38a3fd526964c04199bbc","datavalue":{"value":{"entity-type":"item","numeric-id":1750664,"id":"Q1750664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48abe3dd3339a31110304505e74bd6a601539cc0","datavalue":{"value":{"amount":"+0.8805802","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":"Q1336741$A6AED8C4-3A7E-4E21-860A-1791D74568C5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1336741","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1336741"}}}}}