{"entities":{"Q1818979":{"pageid":1829721,"ns":120,"title":"Item:Q1818979","lastrevid":74282517,"modified":"2026-04-14T19:20:08Z","type":"item","id":"Q1818979","labels":{"en":{"language":"en","value":"Three-quarter approximation for the number of unused colors in graph coloring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1384913"}},"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":"Q1818979$157FDF32-0692-4C2F-8DA6-DAE415CECA65","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"668bbfa7b276595e13d6f77d32c0d01d6f268f3e","datavalue":{"value":{"text":"Three-quarter approximation for the number of unused colors in graph coloring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1818979$11CD6471-C85B-4181-BEBE-D54455B5E8BF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"25f1d84b0e11a739ad3e02d77366043b547b012e","datavalue":{"value":"0937.05044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1818979$4A576190-2321-46A0-9F6D-048A01076B5E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0e06410197cebb6d45b16ed76c4d9f2bd00cba41","datavalue":{"value":"10.1016/S0020-0255(98)10058-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1818979$5637DE37-C166-4613-AE1D-2C1E4D23C054","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"93e6a49c76477086c93fc71581471956184b4ccf","datavalue":{"value":{"entity-type":"item","numeric-id":290185,"id":"Q290185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1818979$2AF888CE-8BF6-4A9B-A89C-B52B60C1D991","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"295c8d206b2110a0a4d0f1d80ba636befef52e19","datavalue":{"value":{"entity-type":"item","numeric-id":290184,"id":"Q290184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1818979$E687601B-F0B2-4CFF-A328-75C20C842C3D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c144f0fb88440afe4b13555aedcc8676a016b6d2","datavalue":{"value":{"entity-type":"item","numeric-id":70466,"id":"Q70466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1818979$2FAD5E9F-527A-4A19-80ED-A25BEC551FF2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f824e8df8660a01a22c6ea772f84f035aa08b14a","datavalue":{"value":{"time":"+2000-06-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1818979$4DB35AEA-08A0-45B7-9DD8-E32835DB5B8B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"66b716f61cc4b6b66734f1ae2bbf1b2ce4bfc494","datavalue":{"value":"Since it is hard to approximate \\(\\chi(G)\\), the minimum number of colors in a graph coloring, the authors consider to approximate the maximum number of unused colors. This approximation is to maximize the ratio \\(r_A=(n-A(G))/(n-\\chi(G))\\), where \\(A(G)\\) is the number of colors found by a polynomial-time coloring \\(A\\) when used to graph \\(G\\). The authors propose a new polynomial algorithm with \\(r_A=3/4\\), which improves the previous result of 2/3. The key part of the algorithm is to approximate \\(n-\\phi(G)\\) with ratio 3/4 for 4-clique-free graphs, where \\(\\phi(G)\\) is the minimum number of cliques to which the vertices of \\(G\\) can be partitioned. The algorithm uses a concept similar to the notion of augmenting path in the classical matching problem, however, more complicated.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1818979$E120168D-EE51-4B0C-883B-C871AF2E4CFB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1818979$C72962A6-E24E-4748-A51C-71CD9CC90C1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1818979$0C92D349-A763-49F3-85C5-C1259DB313AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1818979$6CEE98AD-A908-440C-A965-9B2DFDAA83B6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"deee2fe6dbac80ab9cbeb27c01616cd9ec7aa499","datavalue":{"value":"1384913","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1818979$7D28E040-66F3-4D91-9393-095B647DD756","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1818979$C14D9DD4-8362-4134-80B8-63EB4E456E15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1818979$C779E95B-97F2-4F22-B3A0-62055868D8CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1818979$E08F7B4F-3770-4054-814F-FD4F7010B6F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a153084f07a75cc56b26c617236589c3c4eb947","datavalue":{"value":"cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q1818979$CA49660B-C072-4700-A720-AB0AFF99C330","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcc771f9c4cbb132a4fb9368403bb895cba44b70","datavalue":{"value":"matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1818979$3BD44805-2ED5-426C-89C6-224D40F5ABB1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1818979$C743D64A-DD25-452C-9760-5BEC1B284C9F","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":"Q1818979$5DB2A24A-8E94-47B3-96EC-D6B19AC9B564","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":"Q1818979$34C74910-BBE9-4E6D-AE67-2FC764B16526","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":"Q1818979$6CBBA9FC-53A3-4523-9BA2-98B886E51DE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1818979$0FC751B2-0954-45A7-B4C3-E296177305F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0262c7ca9d46cfb4cf3512f2a0333529706ee62","datavalue":{"value":{"entity-type":"item","numeric-id":3684121,"id":"Q3684121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1818979$948A3DBD-4E4C-461C-877F-23AA5552D435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8993d6ae32dbe0ff01a582fd5d3f3d87a9ac4ef","datavalue":{"value":{"entity-type":"item","numeric-id":1336741,"id":"Q1336741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1818979$94672E4C-C12A-42D0-85BE-58EBEFCC8059","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7342d71003b5a002516681ae764bb29f7737a5d5","datavalue":{"value":{"entity-type":"item","numeric-id":1105385,"id":"Q1105385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1818979$9AF1AE9A-E872-421C-BDDB-ACC377378752","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":"Q1818979$09B110DC-3CB3-4625-8302-36D6995CD112","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5da8aaede631bfdc54d481cb5dea09d28a4412b7","datavalue":{"value":{"entity-type":"item","numeric-id":3763600,"id":"Q3763600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1818979$B88AF081-0B7C-4B9C-9CB7-7672E80644F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44a562aa95e0a07278bdca02b49c4fe5b73f565d","datavalue":{"value":{"entity-type":"item","numeric-id":4144194,"id":"Q4144194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1818979$C0694250-09A9-43F4-973E-34020E43F845","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9b9848781256e3bae4d162be7aa8d4cb8b44fdda","datavalue":{"value":"https://doi.org/10.1016/s0020-0255(98)10058-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1818979$8A0E8177-C45E-40A9-AE2B-D8A103030E1E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"64b7a1415c557a18eba519a29ed51d32ae6152b6","datavalue":{"value":"W2034731049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1818979$5F139E9E-76E1-41BC-8BE3-97133AF87B65","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b44b1d7d4e65dc8c46b51aaf2a941a5832a1133b","datavalue":{"value":{"entity-type":"item","numeric-id":1336741,"id":"Q1336741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66492b72feea97e4f6463b2eb4a01bdafe1140dd","datavalue":{"value":{"amount":"+0.8079802989959717","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":"Q1818979$C2B245DC-0AEF-4AFE-BF8D-63567B7AF2CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d366740438ca32dcb25d35a101e1a57ad3129450","datavalue":{"value":{"entity-type":"item","numeric-id":283679,"id":"Q283679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc3934bb2a2550966e328299c7d1f5a80bddfd9d","datavalue":{"value":{"amount":"+0.8074259161949158","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":"Q1818979$246AB3B6-689B-436F-9BC2-718D6BAED996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2803e5a07fcc4cfd536be4358dfc96be6f071806","datavalue":{"value":{"entity-type":"item","numeric-id":4305670,"id":"Q4305670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0920e8507d59c8447b129aba531411f45f1f3353","datavalue":{"value":{"amount":"+0.7980054616928101","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":"Q1818979$6717841A-0188-4EA8-B123-813BF53040D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e0ce64a68ddb39139af9cb11edd6b372bb98341","datavalue":{"value":{"entity-type":"item","numeric-id":3222860,"id":"Q3222860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f007b408dff1f046f8e980afb0d9b671de5da34","datavalue":{"value":{"amount":"+0.7976230978965759","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":"Q1818979$879399DD-1D0F-40BF-8FE7-679C0BA631E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"648ff0cfbb3c9a6e43115b8fecdb2c9d5c78fb97","datavalue":{"value":{"entity-type":"item","numeric-id":1404543,"id":"Q1404543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c665faed5f66095d4d9d896a42cf14ab79fa48f9","datavalue":{"value":{"amount":"+0.7845202684402466","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":"Q1818979$739510D0-5C7E-4E2B-9097-5DDB982AF5ED","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Three-quarter approximation for the number of unused colors in graph coloring","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Three-quarter_approximation_for_the_number_of_unused_colors_in_graph_coloring"}}}}}