{"entities":{"Q326946":{"pageid":328713,"ns":120,"title":"Item:Q326946","lastrevid":55917439,"modified":"2026-02-21T03:25:22Z","type":"item","id":"Q326946","labels":{"en":{"language":"en","value":"Reducing graph coloring to clique search"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6637985"}},"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":"Q326946$5E34340A-C87A-4A18-B819-D6E03930537E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c9c2f8f5bfef08adcc1fb4a4a7008e8eb83fe87e","datavalue":{"value":{"text":"Reducing graph coloring to clique search","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q326946$D44FE1D7-1116-4F2D-8071-8E5AFD34A168","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fd7ca0ba131de772e6b52f4f42aca7674efb90aa","datavalue":{"value":"1348.05084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q326946$8DF75306-E641-4E07-BADC-C31C1361C60E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f2e2d6572853bc4d9eda9ad825a7188d700dd289","datavalue":{"value":{"entity-type":"item","numeric-id":176454,"id":"Q176454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$054A68FD-1B6A-4EB2-9BE6-416693BF80AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f740aed2f12ef6be463e4f87f7bf1a13adf1039","datavalue":{"value":{"entity-type":"item","numeric-id":326945,"id":"Q326945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$05224211-A5C8-4A78-9BEE-88A14687DCF8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0fd2b14fbd9eacf137e7123f02d62ee42fdc4a3e","datavalue":{"value":{"entity-type":"item","numeric-id":326865,"id":"Q326865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$2701F999-8AEA-423F-A0DC-5D459BC90352","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3345943144ad3fdbe1546c68ad17e7cf0375253c","datavalue":{"value":{"time":"+2016-10-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q326946$F7150230-F96E-4431-B599-1EAEE11339E4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9be6a81ef8a4a7c36b9a06aedc64f8a709297281","datavalue":{"value":"http://apjm.apacific.org/PDFs/3-1-64-85.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q326946$12DC5074-BB42-4690-97B9-69E0BCFD7230","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9c31c4082c4dc9df3988bd59feec2a8ff1c6ede9","datavalue":{"value":"Summary: Coloring the nodes of a graph is a widely used technique to speed up practical clique search algorithms. This motivates our interest in various graph coloring schemes. Because of computational costs mainly simple greedy graph coloring procedures are considered. In this paper we will show that certain graph coloring schemes can be reduced to finding cliques in an appropriately constructed auxiliary graph. Once again because of computational costs involved one has to resort on not exhaustive clique search procedures. These lead to new greedy graph coloring algorithms which can be used as preconditioning tools before embarking on large scale clique searches.","type":"string"},"datatype":"string"},"type":"statement","id":"Q326946$B8049D4A-A354-4D2D-8AD9-A0C550A5C054","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q326946$84745592-34E8-4ADE-B693-3E170F7C7FEB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"088d6b5ae31764df55be83b497952a6bae51cf9c","datavalue":{"value":"6637985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q326946$9945375B-59A6-4E24-BCE3-7163D40D3FE4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q326946$F463FA7D-3971-4F98-BA3B-D61F01C21925","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q326946$0A6A896A-B012-4217-AD86-5CF5B8D1396F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3df54ff4f047dc25d9d99b052a97e79c1184067","datavalue":{"value":"clique search algorithm vertex coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q326946$389BFDB0-7BA2-4363-A36E-75D51154114B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f847e532543d6240537996adb617e8c58f435230","datavalue":{"value":"3-clique free coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q326946$7AA3A791-7E00-49F4-9F13-6333224B732D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1df749b558528d9285d2d971350f9f723845c84","datavalue":{"value":"2-fold coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q326946$88F335CF-3ACA-498F-9D44-CCC123767741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a35970f6c9d25db8fd6157359f5f87a41735c25d","datavalue":{"value":"edge coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q326946$022B6A35-E65A-40A0-B546-ABB74785CDC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"46293a6da34e1d70bbbd4cef906390235c3c2afa","datavalue":{"value":"greedy coloring algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q326946$D1BD8618-7891-4A5D-944A-06E63BD8E0B7","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":"Q326946$D5275532-E1CC-4E93-84E9-65A1132B46C4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fae97d0aee4874e83fbd1d252b645808e0f1d5aa","datavalue":{"value":{"entity-type":"item","numeric-id":1913697,"id":"Q1913697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$3C79990E-4807-43C8-A0ED-85D7484D54B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfa0180fc07b01b5b3a63dd32f85d22b496fa0f3","datavalue":{"value":{"entity-type":"item","numeric-id":3145799,"id":"Q3145799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$0569BE1A-DB22-4CCD-A137-3597B7E555E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e7b26f6765114b169da5a79770389fa5bd84e12","datavalue":{"value":{"entity-type":"item","numeric-id":4175306,"id":"Q4175306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$260D0C44-5F66-4780-9DCB-1117C2F3A82A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3672c9d2d9a732376b2bacc5469a68613a21edb","datavalue":{"value":{"entity-type":"item","numeric-id":922964,"id":"Q922964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$D66006B8-31E9-4D16-96FD-7C8B49ED0275","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d792d7a814e621b32660e5bc12bcdf6e7b4af22","datavalue":{"value":{"entity-type":"item","numeric-id":1310979,"id":"Q1310979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$84D15F0A-31ED-4731-A4D4-FDF885D062E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7245b919a91c2f7b78cccbca02cf24e360b12ef","datavalue":{"value":{"entity-type":"item","numeric-id":5705147,"id":"Q5705147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$8ED49F98-E9E1-4811-9F41-DA2E24E5FE98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5965b20793d5f0fe6b84b5c821604df73f5653f5","datavalue":{"value":{"entity-type":"item","numeric-id":1613374,"id":"Q1613374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$0E7116F4-3654-4D39-A5C1-7E34E4B5E7B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27b91fb34b309a1448e42736f924e3a5012ab649","datavalue":{"value":{"entity-type":"item","numeric-id":3253064,"id":"Q3253064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$409E7F6D-A207-4CE9-81B5-75D0C45B437B","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":"Q326946$FC18B323-E654-49E8-B594-8BE631FA7997","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dc8e3a70353874ae71b2b5e055e522ed5b6378c","datavalue":{"value":{"entity-type":"item","numeric-id":5847741,"id":"Q5847741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$BE220605-C02A-426C-BBF1-EA3BA016A294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$4C20A850-F1A8-4D11-9DBC-60AB62DB6FBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce43a302ed09735ffc850b17ce9dacdfc77edf23","datavalue":{"value":{"entity-type":"item","numeric-id":5395638,"id":"Q5395638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$39360F3C-45B8-40E2-9EAB-8BBB31A9F237","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad9846f13a89559cf0972c91b32ce0b64a6c20a","datavalue":{"value":{"entity-type":"item","numeric-id":1927697,"id":"Q1927697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$E582C00C-7C00-4516-9162-15C418B9647E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31a6695b7e2036bc0bff39440bd5f6f823773e81","datavalue":{"value":{"entity-type":"item","numeric-id":4452109,"id":"Q4452109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$7145294B-C01E-4395-8ADB-E8D206DB2B2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1da15692b7b129bbd5aa6f3835231c364ea3e207","datavalue":{"value":{"entity-type":"item","numeric-id":1267190,"id":"Q1267190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q326946$3EE1AD12-BDD9-439C-B2D0-AB8F545236BB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f7717e85019f4b654d9c1124f0c2421b3f1fd5d","datavalue":{"value":{"entity-type":"item","numeric-id":2422750,"id":"Q2422750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91592a1df85156768fa192bd3204017ec6f4dd47","datavalue":{"value":{"amount":"+0.9767662","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":"Q326946$186307D8-D708-48AA-B778-18B25BC04713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93669ca67aaa6d45608ea6f70ae054c652e70b12","datavalue":{"value":{"entity-type":"item","numeric-id":1744248,"id":"Q1744248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e77786f8d98d7133f83500ae4c98a6123582f327","datavalue":{"value":{"amount":"+0.9091667","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":"Q326946$5E976560-924F-4AE6-95A8-AD6F9958DA5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae740da62f252563edab6a859cb8bc46aaa1aa9f","datavalue":{"value":{"entity-type":"item","numeric-id":656032,"id":"Q656032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29f9f1b95b8abbdbe337fc75d16ca1d5e9a47a7f","datavalue":{"value":{"amount":"+0.90787596","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":"Q326946$2FE3BAF7-1812-40E0-80D5-99642144BABB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd3dd0c186c12c5a250909e526c99aa2cd8c5f1b","datavalue":{"value":{"entity-type":"item","numeric-id":2938100,"id":"Q2938100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"676217912cc9df7c81c9a8d0f27d20370b50da75","datavalue":{"value":{"amount":"+0.9070034","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":"Q326946$EF746616-95B6-402D-975D-2A796DDC3901","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"393b590bbb9c52509abdf50f43ee576769d138d1","datavalue":{"value":{"entity-type":"item","numeric-id":551168,"id":"Q551168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f42625de1c85f5eb3272672d0b583a1967eabb0","datavalue":{"value":{"amount":"+0.89631957","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":"Q326946$5C2F9F2A-B2CE-4D33-BD4E-A4C400655EB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c0898846a5c344bac0d26f630c4f45b9dbaf215","datavalue":{"value":{"entity-type":"item","numeric-id":4019373,"id":"Q4019373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"089273688b17fd64fda129ba9e24a02fedfa8595","datavalue":{"value":{"amount":"+0.8960133","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":"Q326946$C214544F-82A5-420E-B31C-B74AB7A983C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a14407743d48d3795364302c5cb9be7ff68db56","datavalue":{"value":{"entity-type":"item","numeric-id":3088272,"id":"Q3088272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d757e3b9ed1ac09ca27892f54dbbbaf10334b528","datavalue":{"value":{"amount":"+0.89363855","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":"Q326946$A009A9A2-2B28-4CD2-AF6A-B729E903D577","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de976b3945bf0aa0bea51bcf35bcac47cf6d93f0","datavalue":{"value":{"entity-type":"item","numeric-id":393081,"id":"Q393081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d757e3b9ed1ac09ca27892f54dbbbaf10334b528","datavalue":{"value":{"amount":"+0.89363855","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":"Q326946$49063046-5EA0-4E28-912A-1B56E00FCBDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76436cf916c4531a93ce312296e6c4a61a923d95","datavalue":{"value":{"entity-type":"item","numeric-id":4959050,"id":"Q4959050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a3faf9fafbc5016f346e64935b3a1718a090300","datavalue":{"value":{"amount":"+0.88873845","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":"Q326946$D4A0677D-E5DD-435A-93F1-8B32E5A0BB3B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:326946","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:326946"}}}}}