{"entities":{"Q1201260":{"pageid":1212009,"ns":120,"title":"Item:Q1201260","lastrevid":66861693,"modified":"2026-04-12T13:21:38Z","type":"item","id":"Q1201260","labels":{"en":{"language":"en","value":"Covering the cliques of a graph with vertices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 97508"}},"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":"Q1201260$4551B309-1D99-42A2-816D-1141EEAFAB23","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dd82089c5c8cc619e6555a73578bf606dea5c579","datavalue":{"value":{"text":"Covering the cliques of a graph with vertices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1201260$C1912BD6-409A-4445-8F53-D9A5C8795D30","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1adec3a2cdaeea364a3a4c262ac8936df1c4f6c2","datavalue":{"value":"0766.05063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201260$908EDDB5-169C-453F-9EEB-093C90AD0E4C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"883ab3f6f1257e6e35dc9ae9023b4b95887168b0","datavalue":{"value":"10.1016/0012-365X(92)90681-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201260$15D34E68-12BE-4F0A-A4DB-49862FBB1D4D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"17fcd7139afa5567c823530fba22122acb06092a","datavalue":{"value":{"entity-type":"item","numeric-id":175498,"id":"Q175498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201260$610A9B89-A57B-4DED-B39F-60D82F56FA0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb00475fd567190194461a0f087df1793eeae7c4","datavalue":{"value":{"entity-type":"item","numeric-id":6480801,"id":"Q6480801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201260$D715BF98-0EF8-4A82-A963-115581CBE242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2dd88cdf8d0276601ca4e8bc211e877a1701f208","datavalue":{"value":{"entity-type":"item","numeric-id":6482181,"id":"Q6482181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201260$17F0D4D8-A8ED-42BA-89D3-C84914BD9248","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201260$1BBD1FB4-9BA4-47EB-98A3-58FE437AE849","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b0879f591850b4f9f14b2c481d3e08995aa22089","datavalue":{"value":{"time":"+1993-01-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":"Q1201260$66EC0376-F4E2-4A11-95F0-C1650EE04C8E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6d0e4cdf20f2a9597506a9db2fa0891014ef38eb","datavalue":{"value":"Here all graphs have order \\(n\\) and isolated vertics are not counted as cliques. The central problem studied is that of estimating the cardinality \\(\\tau_c(G)\\) of the smallest set that shares a vertex with each clique of \\(G\\). Among other results it is shown that \\(\\tau_c(G)\\leq n-\\sqrt{2n}+{3\\over 2}\\) and a linear time (in the number of edges) algorithm for achieving this bound is proposed. Four associated problems are presented. For example, it is asked if \\(\\tau_c(G)\\leq n-r(n)\\) for all graphs \\(G\\) where \\(r(n)\\) is the largest integer such that every triangle-free graph contains an independent set of \\(r(n)\\) vertices. Also, how large triangle-free induced subgraphs does a \\(K_4\\)-free graph \\(G\\) contain.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201260$E9062548-61A6-46D8-AB8E-31569FFCB1EC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201260$A8F07BD8-90BD-40AF-B3C2-129BCCD23E1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201260$443EF41A-D297-4E77-88ED-2CB18BB1EC56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201260$8916C858-287E-4562-AA8F-52480AF88DD2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"386ef4a6a4b7411fe8b0235f23f4d27a2f8f6ea9","datavalue":{"value":"97508","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201260$C608B104-93CC-4229-A134-8D5C387B08E6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21d142027bf3153eebb876131ac5297907f4e838","datavalue":{"value":"covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201260$3B488EBE-EC8C-4B3D-8C79-4C519599AFB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a153084f07a75cc56b26c617236589c3c4eb947","datavalue":{"value":"cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201260$C22127B2-C365-46EC-A477-0EE826E1E28F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201260$EC465858-8281-425F-BFC7-727C5C51032E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ce67bd27fc3ee89d8642921735100b79f0d0ab3","datavalue":{"value":"triangle-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201260$E3DA5B78-ED9D-47DE-8144-C09F9C3E7369","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f2cf2ab76bfb40a05c985a843284b0a7e39a07e6","datavalue":{"value":"Q105471961","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201260$4A018AD2-2355-4481-90FD-E6C8880E2DC2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4160ba73cc613e2769e008ae8a9ce69c96d8603f","datavalue":{"value":{"entity-type":"item","numeric-id":207053,"id":"Q207053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201260$56748E6B-254A-41B0-AEE5-B4F55A9BF875","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":"Q1201260$E94F3C6E-8ECB-4BA6-BFC1-C1CF67EB347E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"52c7540760fe9ef3923a27be3c87c2aba62dfedc","datavalue":{"value":{"entity-type":"item","numeric-id":1149967,"id":"Q1149967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201260$00C90937-0962-4132-B181-E45C425951B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d974179afb3a4da3b4f27eeba0d09358afcfa28","datavalue":{"value":{"entity-type":"item","numeric-id":810533,"id":"Q810533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201260$530A1E28-56A9-4BBF-9400-D39803A036D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a92ab907df072bb20a1057061523b1fdda43679","datavalue":{"value":{"entity-type":"item","numeric-id":5782525,"id":"Q5782525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201260$1CA81D3F-19F9-4699-8A93-6D22D25E2C13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"747da045d116c192c122bc4a2b3288d773df6c37","datavalue":{"value":{"entity-type":"item","numeric-id":3970967,"id":"Q3970967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201260$C7651FB8-0533-46F7-A9F9-521156750D08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71e85ecfd1a3d32b569447215f150df8b629242d","datavalue":{"value":{"entity-type":"item","numeric-id":3277102,"id":"Q3277102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201260$E9108860-D7D4-4E29-8358-A26A32D2598D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d79cf878065e69a3a1a7c2f5f1f92399af5cbd34","datavalue":{"value":{"entity-type":"item","numeric-id":1098863,"id":"Q1098863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201260$8F501A3A-9242-42EA-8508-11F732C2DCD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ccf2ce6ffe932287a3e8f6d3b281b44fd4ad0eb","datavalue":{"value":{"entity-type":"item","numeric-id":4770411,"id":"Q4770411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201260$97F195DC-A6A5-46CF-A9E1-06EF684B3AAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00b79ce7beb3596052714e5eb40fbfabb9a3ecac","datavalue":{"value":{"entity-type":"item","numeric-id":1174130,"id":"Q1174130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201260$0D57520E-AD50-428B-8A43-44E593CAFF7F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"92def890686237610a1d74b92a70b70b973d8db8","datavalue":{"value":"https://doi.org/10.1016/0012-365x(92)90681-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1201260$5CA852DA-19EE-46BB-923C-BDE7FB4149DD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bba700f6c3f369472924b2dbfcdfea93db73dd85","datavalue":{"value":"W2086357278","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201260$D1A0C259-96F8-4FCD-BE0E-E2B95147B5EE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6febd4f652834fc534e13376fde58de9dade7380","datavalue":{"value":{"entity-type":"item","numeric-id":3944641,"id":"Q3944641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0318324c27b4eac65cc17b6c92734d2eb380d44f","datavalue":{"value":{"amount":"+0.8145330548286438","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":"Q1201260$0F36A1DA-1C01-4F33-BAE2-B26269FB0B3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad6d72508f1dddd463917306d42c15616d08c6fa","datavalue":{"value":{"entity-type":"item","numeric-id":4726289,"id":"Q4726289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aab74ec450cbbf08794ba9ef61e00ee99bd5dfb1","datavalue":{"value":{"amount":"+0.8041713833808899","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":"Q1201260$FF14B713-46DC-4554-B830-6C2FC4E18E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2e77b6a64615473518971f7c037cc35ec1636ad","datavalue":{"value":{"entity-type":"item","numeric-id":1100482,"id":"Q1100482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e764236531f8409e26ef32da6a3246ca2cac6003","datavalue":{"value":{"amount":"+0.7940500378608704","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":"Q1201260$A4FBA4F8-43A2-42E4-805F-343A735655B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9fc72d2afefb0d100f0dcf4c4e1a6785609352b6","datavalue":{"value":{"entity-type":"item","numeric-id":1174130,"id":"Q1174130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35c7c18b8c5cfac9eb2f0a4d53a6b06821f4f8ff","datavalue":{"value":{"amount":"+0.7939084768295288","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":"Q1201260$A4A5DE99-9B0C-4EB4-A922-9768A58E9B97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76e0f4d0f674ec24869b9c44a07bcad5ee90bdc3","datavalue":{"value":{"entity-type":"item","numeric-id":700383,"id":"Q700383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34783c53b6db1389bbeb0cd2448a25d0f3c87ba8","datavalue":{"value":{"amount":"+0.7913936376571655","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":"Q1201260$9983AF63-3084-43F7-B946-7EDC8BAA05B4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Covering the cliques of a graph with vertices","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Covering_the_cliques_of_a_graph_with_vertices"}}}}}