{"entities":{"Q1927697":{"pageid":1938439,"ns":120,"title":"Item:Q1927697","lastrevid":69694467,"modified":"2026-04-13T08:46:17Z","type":"item","id":"Q1927697","labels":{"en":{"language":"en","value":"Greedy algorithms for triangle free coloring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6120581"}},"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":"Q1927697$353474A2-C737-41C4-88F9-3BCA7E548241","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"118bcbb50005b9ea1e590804b7f53eb2e8410513","datavalue":{"value":{"text":"Greedy algorithms for triangle free coloring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1927697$5F85DF2E-794F-4050-A9A9-BDC20A9A1D60","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"37bdb225d24de3d7687c9ca47a9fe14ca6baf99b","datavalue":{"value":"1262.05063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1927697$5A3D09C2-1099-4647-8B4D-CDBBE8E92E07","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"03e0344fac3b71001f7d01722f599a45a6c3dae0","datavalue":{"value":{"entity-type":"item","numeric-id":321980,"id":"Q321980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1927697$A12E64DD-12B6-4EE3-AE80-656D2177FCDF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d9e78dc582cccb265eec7a023159b5315b28fd05","datavalue":{"value":{"time":"+2013-01-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1927697$F89B0B86-1809-4FF0-BF7D-AAB83DA2A9CC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3b2c4a60065c7319eb426617bf447a8d819cfb4f","datavalue":{"value":"It was shown by \\textit{I. M. Bomze}, \\textit{M. Budinich}, \\textit{P. M. Pardalos} and \\textit{M. Petillo} [``The maximum clique problem,'' Du, Ding-Zhu (ed.) et al., Handbook of combinatorial optimization. Suppl. Vol. A. Boston: Kluwer Academic Publishers, 1--74 (1999; Zbl 1253.90188)] that in order to design an efficient algorithm for listing all the cliques of maximum size in a graph one must be able to find tight bounds on this size. To this end, the article under review introduces some new colouring schemes using \\(s\\)-clique free partitioning; that is, the subgraph induced by the set of vertices that are assigned the same colour does not contain a clique of size \\(s\\). For \\(s= 3\\) we have a triangle-free colouring. It is shown that it is NP-hard to decide whether a given graph has an \\(s\\)-clique-free colouring with \\(r\\) colours for any \\(s\\geq 2\\) and any \\(r\\geq 3\\). Several algorithms are presented for finding triangle-free colourings that use approximately the minimum number of colours, including two greedy algorithms and some satisfiability solvers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1927697$C1E4B169-3941-4F75-934E-64A998FDEE37","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1927697$8857FF40-9321-4C6E-BC4E-9E4C0C105B19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1927697$D427ACA8-C40D-4FE3-9EE4-6A8689434C91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1927697$4EF427BD-18DA-4CEA-B026-6F42091CA948","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4ab31e59eb90fe94456224f8ee02e3aba74cac1f","datavalue":{"value":"6120581","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1927697$EFD41939-A871-421C-9EAC-784AD383A5F6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1927697$1ED965AF-9A0A-4F46-B437-928AB5CE4C09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44a181c7b2997b4e3846dd20fd7f7cfe8269ff11","datavalue":{"value":"maximum clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1927697$3713C44D-7146-4709-9074-6173992EBEE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1927697$54D9F685-90EF-4AA3-AA5E-FED934D902D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85dfdbd7a975d6137b355769addaba184ea21dc4","datavalue":{"value":"vertex coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1927697$121DD1F6-6F1F-448B-9F7B-6AC708B8B8DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eef3ec386a56d81ff07774c6459ede8a98539aff","datavalue":{"value":"\\(s\\)-clique free set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1927697$6AB66560-23CA-46B2-BB6A-364D9C7D215D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c880bea00f32d586813db1d2f107e4da760f8b","datavalue":{"value":"\\(s\\)-clique free coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1927697$2CBAA764-3828-445E-8296-7B21690CC809","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fcd381fa6885903307320f40ad20fffe6cc9db47","datavalue":{"value":"clique search algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1927697$D62825A4-B8C2-4473-8FAC-C6E756C7371A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3bc75a928070083350b50b0bf776e72891bd169a","datavalue":{"value":"satisfiability solver","type":"string"},"datatype":"string"},"type":"statement","id":"Q1927697$67355E73-265C-4DE5-A9F9-7BD3CFBC27F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"834ef099fddf744c066723f952f8e825befc12c4","datavalue":{"value":"greedy coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1927697$DBCD3D93-2108-49DE-9025-28C4445A728F","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":"Q1927697$F321585B-27DB-453D-94CB-439EB3CF76E0","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":"Q1927697$396D0DDE-C8DA-4E04-AD8A-E443AD2C1676","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1927697$DAA8D674-FB29-49B0-9907-A176DEB9201F","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":"Q1927697$0AAD6DD8-2492-49D4-B20E-CEA9EA9EA0E4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d5532fc5495154adad1b08303e655fe57b63cba","datavalue":{"value":{"entity-type":"item","numeric-id":3057624,"id":"Q3057624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11c375ee899bc4fa0062a37e744ec70fe955030a","datavalue":{"value":{"amount":"+0.7993360161781311","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":"Q1927697$D3960DE2-4992-40C0-B836-E396F6A28F32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89dacd94fc24813bd4cf458d3d0cd2cdc474ef5c","datavalue":{"value":{"entity-type":"item","numeric-id":1356685,"id":"Q1356685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5785bced1b176e2768c74adc37dcb24eac9ea1c3","datavalue":{"value":{"amount":"+0.7923173308372498","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":"Q1927697$EF56811C-D68E-475C-A45B-246D17D74CB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34ea8d68e43770628bff974bab298c644414a2aa","datavalue":{"value":{"entity-type":"item","numeric-id":1957652,"id":"Q1957652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"240818257bb551b81e7c14d31bc712842ef6dbbb","datavalue":{"value":{"amount":"+0.7838214039802551","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":"Q1927697$40EE3388-FEA5-4D67-8C2C-13ACFD28072A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"908f3fc5ea5bda8bed54101057493c483a1adc88","datavalue":{"value":{"entity-type":"item","numeric-id":4652597,"id":"Q4652597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdd42f9de23aa5e3db4c3f7163cffa78afc53a43","datavalue":{"value":{"amount":"+0.7801784873008728","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":"Q1927697$C27C1A7A-D2AB-411F-8366-83B037906F37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56316c239f530a8aca906a4ced710f2bc794157b","datavalue":{"value":{"entity-type":"item","numeric-id":4916101,"id":"Q4916101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fa2877390ccc9441fa578b0f36de388ddae62be","datavalue":{"value":{"amount":"+0.7784621119499207","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":"Q1927697$651EE487-E217-4395-A99E-FCAE2C818DEB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Greedy algorithms for triangle free coloring","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Greedy_algorithms_for_triangle_free_coloring"}}}}}