{"entities":{"Q820840":{"pageid":822688,"ns":120,"title":"Item:Q820840","lastrevid":56685861,"modified":"2026-03-18T19:57:37Z","type":"item","id":"Q820840","labels":{"en":{"language":"en","value":"Tight bounds on the clique chromatic number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7402030"}},"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":"Q820840$F43F57B3-362B-4A20-9B7D-08A1D35A1D85","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1e4c095db8ddb3654b850c100cf3c8f1d96f3529","datavalue":{"value":{"text":"Tight bounds on the clique chromatic number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q820840$800E0D33-5275-42F6-9901-52F7ACFA2137","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a9e12045b40c82d373effbfad1f4673b6977b386","datavalue":{"value":"10.37236/9659","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q820840$FC8C5D48-13F8-4850-9E73-266358913664","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb1d48e699dcbd07426b1c3ee3831813e5c5d7b0","datavalue":{"value":{"entity-type":"item","numeric-id":412238,"id":"Q412238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$5EC70980-D0FE-428F-9670-AB051F3BFCC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4cd896cc324ed8d238532cc31bb366d571b9dcae","datavalue":{"value":{"entity-type":"item","numeric-id":377498,"id":"Q377498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$7706EAA5-FB56-4080-B71C-26F7D2BDC572","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d98a938c7c496671aebe9d069bbd3d70f74a635a","datavalue":{"value":{"entity-type":"item","numeric-id":661944,"id":"Q661944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$6EB8389E-03C0-48F3-BD81-67E4321477CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad5167b666b6ff8ea720dcdbc03cbe41b9c51f06","datavalue":{"value":{"entity-type":"item","numeric-id":582044,"id":"Q582044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$CB4F44C6-FF5A-460B-82CF-FBDCD619AFED","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$E7F170AA-D006-4730-BD62-CC16ECE948F1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b1e0a20a85c4acee032772bf87985ac88d544c33","datavalue":{"value":{"time":"+2021-09-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q820840$6EE7E789-C1FF-453B-9628-4A948BA39D06","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d6dfa02b1c7d3f6eb0a2071db19c340aae987e72","datavalue":{"value":"https://arxiv.org/abs/2006.11353","type":"string"},"datatype":"url"},"type":"statement","id":"Q820840$5EF64CDD-CBDC-416F-A852-B43A07B38B21","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"38ee61c6ec2abb7a95729b676ef6939339434cdf","datavalue":{"value":"Summary: The clique chromatic number of a graph is the minimum number of colours needed to colour its vertices so that no inclusion-wise maximal clique which is not an isolated vertex is monochromatic. We show that every graph of maximum degree \\(\\Delta\\) has clique chromatic number \\(O\\left(\\frac{\\Delta}{\\log\\Delta}\\right)\\). We obtain as a corollary that every \\(n\\)-vertex graph has clique chromatic number \\(O\\left(\\sqrt{\\frac{n}{\\log n}}\\right)\\). Both these results are tight.","type":"string"},"datatype":"string"},"type":"statement","id":"Q820840$0F47A178-295A-4439-8899-488443BF2AC6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q820840$36162F3A-7340-4341-AF31-59A500989358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q820840$715FD87E-57F0-4212-8C38-C5D083FCF4E4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b56138b7c61a48bf2e41ec03e8fc405509283827","datavalue":{"value":"7402030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q820840$4BBBBB37-165D-4985-B6B5-586AFC5885C5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08a6a77ff815ead7c5168e74cb7b7389de8bdd22","datavalue":{"value":"clique colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q820840$630084EE-82FE-4779-8E12-643582BF397F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q820840$FB1AFC11-6354-4802-956F-046085768DE7","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":"Q820840$75FA7D94-56A3-46A0-9E3E-F606D5270402","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b49c10465299c9db99596bd69b1b6dc0e318dee3","datavalue":{"value":"W3036334018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q820840$56C89AF4-77D0-4E47-8981-F87077ADC3B2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5b82f7b1a4073bc4c9f0009d3df8c0e8eb8773b","datavalue":{"value":{"entity-type":"item","numeric-id":4652597,"id":"Q4652597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$2FD2035F-1CD8-431A-92DC-C4F1984726A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3f5cfeb33b82e5b830922f483b6ce05fc8bf549","datavalue":{"value":{"entity-type":"item","numeric-id":896010,"id":"Q896010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$15EC6FC1-F228-40B4-9416-19345E47E68F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4276199f337e80f22cd0a037a4918c76805dbf80","datavalue":{"value":{"entity-type":"item","numeric-id":1176381,"id":"Q1176381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$1E5EBE9A-61D2-4E4D-96F2-DCB574D116DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9761a0cc19f897a3746927037f04b504c7b4310a","datavalue":{"value":{"entity-type":"item","numeric-id":1177956,"id":"Q1177956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$065079BC-2293-45A0-9EE0-95EF2204D6B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7c4c6fcf7632d7a047bb07649c69c1cbae53c1d","datavalue":{"value":{"entity-type":"item","numeric-id":5957752,"id":"Q5957752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$E9AFD5BB-8F94-4F68-ADB5-B6D3C6503711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"679cd69ecfc8ce3cb01edf955ed484b70cab75ad","datavalue":{"value":{"entity-type":"item","numeric-id":2822602,"id":"Q2822602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$3D2BFAAD-373F-4300-B5DF-650CFD3D086A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15132b3e75729a6d081fd45a4b035add2a9fce88","datavalue":{"value":{"entity-type":"item","numeric-id":4851927,"id":"Q4851927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$F4824332-B5F3-4E51-9372-B93F04DC75E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aacbd1715694c028de1eaa00529f027c2eb7ee8c","datavalue":{"value":{"entity-type":"item","numeric-id":5229333,"id":"Q5229333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$88614EFD-C554-4321-8516-332BEBB63F6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65fe1f39a80493cba406edeba3e15c0e73ff653a","datavalue":{"value":{"entity-type":"item","numeric-id":1292236,"id":"Q1292236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$11484D93-4C32-4AC0-BBA7-2711D66D8DD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4bdab85ea6abb667b054a34d741cead315dd35e","datavalue":{"value":{"entity-type":"item","numeric-id":1633755,"id":"Q1633755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$E67BC4DF-81A9-42BD-B850-BE1851DFD6F9","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"8113402dfd4f02c2bd8f9a59dc2cb93eb9983431","datavalue":{"value":"bafkreigrfy7ztowiyirdsbcjrxsw3rgfbqnn7ptbskcm6bptjmkbr23m3a","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q820840$AA5F5997-C1EB-45C0-A11C-4433CB429788","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbf3beaae05ff3d4db27a619151310423830f855","datavalue":{"value":{"entity-type":"item","numeric-id":4581274,"id":"Q4581274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6988de5f387d511a6a8ac2c4e0c8f47aa0c2f49e","datavalue":{"value":{"amount":"+0.8402979373931885","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":"Q820840$D04B462F-F037-48E7-BD6B-54E7FF92528B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f173b6dc2a79568a012ba25cdc071f872c111d3d","datavalue":{"value":{"entity-type":"item","numeric-id":6074590,"id":"Q6074590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad90cd32b9f9b864bdc63fff7922e6ceafb7e8f8","datavalue":{"value":{"amount":"+0.8385694622993469","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":"Q820840$A265E91F-8DC8-4A8B-9638-601AA5E9638A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4827171251d1d48bdeea8582d7270cb0c5860e98","datavalue":{"value":{"entity-type":"item","numeric-id":5229333,"id":"Q5229333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36e5cb54b347e46f6b3c9a161615dc7005d62ad9","datavalue":{"value":{"amount":"+0.8335908651351929","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":"Q820840$A5391C68-6F5D-43FC-B271-C23CE9B3B61E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56a6f60919d54a71297b476739cad437339d2343","datavalue":{"value":{"entity-type":"item","numeric-id":2945676,"id":"Q2945676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abea3ed1f3e330b6666605478e51bf6d9d3d370f","datavalue":{"value":{"amount":"+0.8320736885070801","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":"Q820840$BFEC708D-124C-43EB-867E-D1EA80B36A6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96cd1b44c6a3ae82c418e25645d5938c00a669c3","datavalue":{"value":{"entity-type":"item","numeric-id":2192124,"id":"Q2192124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dca5854245d7e0f47d907f1232cc09a45f00ce33","datavalue":{"value":{"amount":"+0.8259421586990356","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":"Q820840$C791BDD1-030A-4C90-94BD-D08A0B55BF7D","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q820840$1736249D-5B34-48FD-8291-A56624DCF29B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:820840","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:820840"}}}}}