{"entities":{"Q2288355":{"pageid":2299098,"ns":120,"title":"Item:Q2288355","lastrevid":57814305,"modified":"2026-04-02T15:47:28Z","type":"item","id":"Q2288355","labels":{"en":{"language":"en","value":"Towards Erd\u0151s-Hajnal for graphs with no 5-hole"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7153030"}},"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":"Q2288355$624A2941-E662-4985-95D2-B306E291B93D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ce75e021d6de68ec4c38b4dc5877149790845555","datavalue":{"value":{"text":"Towards Erd\u0151s-Hajnal for graphs with no 5-hole","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2288355$0D49796C-19AE-4A1C-8A4D-89708D1576D2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a59d11487f9ee91759c689cde49a13dceb1b8707","datavalue":{"value":"1449.05148","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2288355$E0BD8582-DA5B-499A-8F8B-CFBDF9830CE6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86791d2de8f741697c1a28c841b5e520b1ea6f17","datavalue":{"value":{"entity-type":"item","numeric-id":256974,"id":"Q256974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288355$DF8240DA-64E7-4480-8CB4-C708EBF1FDB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"576bcceabff8dce115427e52f43e894dfd6284df","datavalue":{"value":{"entity-type":"item","numeric-id":290804,"id":"Q290804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288355$69B5AAF6-5EF7-4A71-957A-8C65ACB2FAFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f84c2585906a3dfec8dc78c048cfc8b3b8be2285","datavalue":{"value":{"entity-type":"item","numeric-id":345122,"id":"Q345122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288355$5F2C90DF-76A7-4D5C-A313-435C4578A992","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f8b2beaa85ff67f6ba8323eb17002460f5e5f0aa","datavalue":{"value":{"entity-type":"item","numeric-id":846045,"id":"Q846045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288355$74499D49-81E1-4185-A369-29AE117C9F63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b7666b1aea36d852e5d73efdf8f9faa64e3f54f","datavalue":{"value":{"entity-type":"item","numeric-id":705887,"id":"Q705887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288355$53538758-4D10-46C0-887C-613F38B0F5C8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288355$59CF299B-ACC1-4544-B851-5CE67D222E32","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8a6a5b5fdeb4bedfada8cbabb8db67346705498a","datavalue":{"value":{"time":"+2020-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":"Q2288355$AE5C6298-7A65-4073-8D42-B19277A27243","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"688f958e5cde5667d7cc27bb621620386cae3558","datavalue":{"value":"https://arxiv.org/abs/1803.03588","type":"string"},"datatype":"url"},"type":"statement","id":"Q2288355$60022408-DF91-4B68-9DE1-D0E0AF5BBBCF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"47008e7a67980ad59e5aadd5ecc11a025c9b50b9","datavalue":{"value":"In this paper, all graphs are finite and have no loops or parallel edges. The cardinalities of the largest stable sets and cliques in a graph \\(G = (V, E)\\) with \\(|V|=n\\) are denoted by \\(\\alpha(G)\\) and \\(\\omega(G)\\), respectively. For two graphs \\(G\\) and \\(H\\) we say that \\(G\\) contains \\(H\\) if some induced subgraph of \\(G\\) is isomorphic to \\(H\\) and \\(G\\) is \\(H\\)-free otherwise. The Erd\u0151s-Hajnal conjecture says that for every graph \\(H\\) there exists \\(c > 0\\) such that \\(\\max(\\alpha(G), \\omega(G)) \\geq n^c\\) for every \\(H\\)-free graph \\(G\\) and this is still open when \\(H=C_5\\) (\\(C_5\\) denotes the cycle of length 5). The best general bound for the Erd\u0151s-Hajnal conjecture to date \\(\\max((\\alpha(G), \\omega(G)) \\geq n^{c \\sqrt{log(n)}}\\) was proved by \\textit{P. Erd\u0151s} and \\textit{A. Hajnal} [Discrete Appl. Math. 25, No. 1--2, 37--52 (1989; Zbl 0715.05052)] for every \\(H\\)-free graph \\(G\\) (logarithm is of base 2). This was also the known bound for \\(H = C_5\\). In this paper, the authors improve the bound to \\(\\max((\\alpha(G), \\omega(G)) \\geq n^{c \\sqrt{log(n) log(n) log(n)}}\\) for every \\(C_5\\)-free graph \\(G\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2288355$8F92B70B-420D-477E-8311-B96BBB691D43","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2054ab6afcff86345461ab192c34bfbef6c7b38d","datavalue":{"value":{"entity-type":"item","numeric-id":261055,"id":"Q261055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288355$24C0BE1E-F4DC-4454-9881-0DC11AF17391","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2288355$EB4B9CD8-89C4-4058-B8E7-6E14A3B56ED2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2288355$D76882E5-3BFC-469C-8517-45136F3149B1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6752dda90a9794f138222b5631fa0e4be27d4969","datavalue":{"value":"7153030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2288355$F90739FA-4612-4621-9938-6E5E5DBAFBE5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"191403835f9d573ead779b7e37a9e1db540852cc","datavalue":{"value":"extremal problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2288355$6268BD72-E943-446A-B999-2D6D110F958D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6dd0d7043066fc18c97c64cc2373bc266c0fadc1","datavalue":{"value":"stable set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2288355$69C94915-A12C-48C3-B5B5-0EC83D901408","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a153084f07a75cc56b26c617236589c3c4eb947","datavalue":{"value":"cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q2288355$747DBE55-59CF-450E-B5D9-7D01CBCDB8FE","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":"Q2288355$B594E7AF-6B8D-4B83-A478-2247E5312253","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cf81fd1461307ed4662ac1e5d0920247d6419379","datavalue":{"value":"W2978963187","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2288355$B45D64E3-4DDB-4337-80D7-D250D73297F4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9afc9f302572ec131c968321d12c23b5af654288","datavalue":{"value":"10.1007/S00493-019-3957-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2288355$9A2B6EF2-A683-4AC9-AF03-487A7B55BB5F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd92e8ec49c06a9a1935113a62df759cb7906af4","datavalue":{"value":{"entity-type":"item","numeric-id":2874098,"id":"Q2874098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"494744890bd1ca4ef0f24b12144d7d81711dd075","datavalue":{"value":{"amount":"+0.82988435","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2288355$68699B8A-D61E-4C47-A621-3BEE39EA381F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10c81cdb3d275b16526471eb086e643cf29e1ada","datavalue":{"value":{"entity-type":"item","numeric-id":2813338,"id":"Q2813338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d8a4ac479b381408eb1f48076cb484e428ec08a","datavalue":{"value":{"amount":"+0.8131678","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2288355$15F3FCBB-0261-4EBA-AF90-4B8206C02763","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bae5298e279ca7b08bc1b25469b917d9748f34a9","datavalue":{"value":{"entity-type":"item","numeric-id":6075068,"id":"Q6075068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72027a547e8d7313df38741bd96950e27c777ebc","datavalue":{"value":{"amount":"+0.8088955","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2288355$590238E5-2A71-4104-A5F3-6904EA61B3D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6d853657f23d7b0e9e72ff42cc3b30d95bab21d","datavalue":{"value":{"entity-type":"item","numeric-id":2911494,"id":"Q2911494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de756dbd613fcc73780418fe86f2b4a6600358c3","datavalue":{"value":{"amount":"+0.79799664","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2288355$21A22AED-B657-4AEB-B33B-E81151664818","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05d1c5be336f3df3eb0c620927f9c39c28e56046","datavalue":{"value":{"entity-type":"item","numeric-id":520043,"id":"Q520043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9563815f7a8222f48eb9185a182da7e6957fb5d","datavalue":{"value":{"amount":"+0.7943661","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2288355$1863E9C2-967F-4F6B-B67D-413245332A38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96037a78b3549ce9d98f83207289fc9a03cfd940","datavalue":{"value":{"entity-type":"item","numeric-id":990082,"id":"Q990082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59503a2e27fb98ca5993291b87f18332526d054c","datavalue":{"value":{"amount":"+0.7840764","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2288355$CC1D5FE8-215F-4B49-AF32-6AC2F425441A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a776f4cf691f55803ee3ae877e82c50bc96285e","datavalue":{"value":{"entity-type":"item","numeric-id":1984528,"id":"Q1984528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8db442cb1d0ec2fd207623676a5347b7a7608d17","datavalue":{"value":{"amount":"+0.7829213","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2288355$5AE13260-62A1-4088-988F-16F9174A22FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e87acf4f844d77b86bbd0a616fb6e9ad53bea3bf","datavalue":{"value":{"entity-type":"item","numeric-id":5199419,"id":"Q5199419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1039f2072ed423bda5b6025460accc3b58618e3e","datavalue":{"value":{"amount":"+0.76964754","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2288355$BDC1406D-C042-4B54-9D48-82A76AF8C08A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26551de1f744f24427aa4afcfed43c7efeab275b","datavalue":{"value":{"entity-type":"item","numeric-id":5325947,"id":"Q5325947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc06e255c603fc1287c17a2a50252f0e0b1a8018","datavalue":{"value":{"amount":"+0.76743793","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2288355$E89DB318-4C04-4B7E-B785-9FFC55ECCBA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d94d7fc01d9a5a7ad5221ba46d392d4b0bb4fb3","datavalue":{"value":{"entity-type":"item","numeric-id":993683,"id":"Q993683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86491f2826032255cddd1987ea71c7a407bb6698","datavalue":{"value":{"amount":"+0.7583039","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2288355$4B597BAE-C269-42A6-B598-3F97C8B9F6FD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2288355","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2288355"}}}}}