{"entities":{"Q2185224":{"pageid":2195967,"ns":120,"title":"Item:Q2185224","lastrevid":57758256,"modified":"2026-04-02T09:51:26Z","type":"item","id":"Q2185224","labels":{"en":{"language":"en","value":"Bipartite induced density in triangle-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7208432"}},"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":"Q2185224$C52086A5-0C99-438B-89BE-FE8B178EBB71","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f9c486536b09b40666d7de3dbc0ff751b8508554","datavalue":{"value":{"text":"Bipartite induced density in triangle-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2185224$169357D7-5DC0-41AF-8E8A-B8656FAEAD70","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"96100c53600b4662062dbc7f167a34070ca36f4e","datavalue":{"value":"1441.05119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185224$E1C60E0F-B4C9-47D0-B05D-908A3DFC0231","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"92d506228992ab046f90f44d61c2fe0684f42c9a","datavalue":{"value":"10.37236/8650","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185224$CE807FC9-6AE9-4222-90AF-6ECBCDD4D325","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"27f395011aa493efae03e55f34e56a09b84a5adc","datavalue":{"value":{"entity-type":"item","numeric-id":1689910,"id":"Q1689910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$896665AD-1284-4868-9D4D-5B0EDC04B544","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"41c9884f9185e98e861086ad404003fff6b8f87c","datavalue":{"value":{"entity-type":"item","numeric-id":1689947,"id":"Q1689947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$92067F1E-CB26-4E74-9C53-6EADBBFAF668","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7edc88cd7c31e9f658112ad12d8326f495a0c303","datavalue":{"value":{"entity-type":"item","numeric-id":324378,"id":"Q324378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$F9D0C14C-70EF-422B-A232-157423C041C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c97872338b7fe4c052d76717824db3e77f4ce574","datavalue":{"value":{"entity-type":"item","numeric-id":1689994,"id":"Q1689994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$0402C0FE-C6D1-42C3-8CEB-3659F6338915","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":"Q2185224$243D08B0-ACA7-41E6-964B-0C68BE9E672B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"84fdf3ed3ab7383ca4f016ac37ce5ef0ef7cb738","datavalue":{"value":{"time":"+2020-06-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2185224$9A9A5F72-1545-46C6-9BA3-D151D95DE5F3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0dca1b036edbaa4b230dc0f51eacb0bc86e15cfe","datavalue":{"value":"https://arxiv.org/abs/1808.02512","type":"string"},"datatype":"url"},"type":"statement","id":"Q2185224$5C7E8C0B-1BB8-4A05-ABF7-DC40E19AE172","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"be0b22c0a73a4738bfece12a2be7ad98d80d1155","datavalue":{"value":"Summary: We prove that any triangle-free graph on \\(n\\) vertices with minimum degree at least \\(d\\) contains a bipartite induced subgraph of minimum degree at least \\(d^2/(2n)\\). This is sharp up to a logarithmic factor in \\(n\\). Relatedly, we show that the fractional chromatic number of any such triangle-free graph is at most the minimum of \\(n/d\\) and \\((2+o(1))\\sqrt{n/\\log n}\\) as \\(n\\to\\infty \\). This is sharp up to constant factors. Similarly, we show that the list chromatic number of any such triangle-free graph is at most \\(O(\\min\\{\\sqrt{n},(n\\log n)/d\\})\\) as \\(n\\to\\infty \\).  Relatedly, we also make two conjectures. First, any triangle-free graph on \\(n\\) vertices has fractional chromatic number at most \\((\\sqrt{2}+o(1))\\sqrt{n/\\log n}\\) as \\(n\\to\\infty \\). Second, any triangle-free graph on \\(n\\) vertices has list chromatic number at most \\(O(\\sqrt{n/\\log n})\\) as \\(n\\to\\infty \\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2185224$014A0589-8715-4CA7-8E88-25F2A078D60E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185224$9A4A6402-F394-41E8-85A8-6FCEAD32363C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185224$5AC8185F-7E0C-47E7-A019-A224F8AA3248","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"de1e23711e724f0ddec470e09670addfca72494a","datavalue":{"value":"7208432","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185224$19F662D1-A22B-4A17-B6E9-A21A895CA409","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"637872e1bd0dd812655871ae455bcab7bf55fd2b","datavalue":{"value":"fractional chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2185224$EBA540FE-48BE-4AF6-BE7B-CA7B560B5622","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29b2fd1ad1651ff359de646b08e8af5d522bc3c2","datavalue":{"value":"list chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2185224$D3172918-CB5E-45CF-96D4-8E84C8AA70B8","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":"Q2185224$EC6E5BBE-550B-4A3C-ADF9-0DE8F7D3ACAB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b654afad0ca0d47f9e1e21f867df9bd8f9cdb7e4","datavalue":{"value":"W3029889037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185224$1D62B3BD-4F3F-4557-B725-216C834D2D06","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d718202177874559acaa759051aa392027bdc43","datavalue":{"value":{"entity-type":"item","numeric-id":1159234,"id":"Q1159234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$DFF68C0C-AC7A-4210-9016-0A5385E167DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed7ec6f0e6329fc3509021e1635ba44b02e95ce5","datavalue":{"value":{"entity-type":"item","numeric-id":4291205,"id":"Q4291205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$11CC0F85-E94B-4C1F-B95D-3A9E1A37FA19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73e5909188526138317dd48531e52bdc058b1f00","datavalue":{"value":{"entity-type":"item","numeric-id":5420011,"id":"Q5420011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$1CB1EC90-33D9-457E-93C3-2A09209FFB15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0d3f4dd178aa05cc4811ab84eb9f13d7858fd8d","datavalue":{"value":{"entity-type":"item","numeric-id":5136931,"id":"Q5136931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$F1E8EDF3-03DA-4629-8631-F21B0B067612","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":"Q2185224$BD2A6C65-15D6-4431-9422-4C1CA020E88A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfd76d3b25c59283432b709b4727c19b8f5be7cb","datavalue":{"value":{"entity-type":"item","numeric-id":1059084,"id":"Q1059084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$C1DA5B14-31C7-418E-963B-B0980FFBB5EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03ef46efd22e4c58a8ba7f3f8e6dd19d883363a6","datavalue":{"value":{"entity-type":"item","numeric-id":2562797,"id":"Q2562797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$76AC6904-B824-4F83-BD51-299D7D61843F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f710fb9bade0b07448e71c00da7f3066b97801f","datavalue":{"value":{"entity-type":"item","numeric-id":5222550,"id":"Q5222550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$555DF01C-DC1C-4390-B267-C686EAC5769B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8533499f7ff81508e8ebd49ceeba88a0de19c7f0","datavalue":{"value":{"entity-type":"item","numeric-id":5108704,"id":"Q5108704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$41E209DA-B2B9-4B7D-B78C-25373F1064CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f1def122e6b91e0c939a395d3347c347f2b3db6","datavalue":{"value":{"entity-type":"item","numeric-id":1567684,"id":"Q1567684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$452DCC22-B0D4-4889-AEDE-3767B2953499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$B6386DA6-4BD3-444D-8318-1AC7697A7ACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f855246caf01e7d423da5ddcd02591be6660a7f0","datavalue":{"value":{"entity-type":"item","numeric-id":4857375,"id":"Q4857375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$BC54B150-C9CA-4083-A542-7EFCB9AB7BA2","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":"Q2185224$39958BEC-155D-435D-A7B0-7CB3B4723154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12182e03e631310f152cece2f034e9b5a45d47ba","datavalue":{"value":{"entity-type":"item","numeric-id":2003768,"id":"Q2003768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$7CFCF5CB-7165-469F-8DFA-07D337AF50AD","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":"Q2185224$54382A98-DEC0-4639-9615-DE00A3FDC45B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98569c781cb0dbf8d89137f80b99301798aa409a","datavalue":{"value":{"entity-type":"item","numeric-id":1969797,"id":"Q1969797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$CE9CE418-825C-4B47-AC6C-B46FCFFB2C9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af00a885711522a52a7e14d7f7ed5d6aa1677476","datavalue":{"value":{"entity-type":"item","numeric-id":4296525,"id":"Q4296525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$B328486B-2851-4F38-A759-B4D4CACA114F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fad64547aa8c484ae73fda6b3bc2f85436a1625d","datavalue":{"value":{"entity-type":"item","numeric-id":1052343,"id":"Q1052343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$C2373B06-C014-4F23-BF1B-64A558C23BCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42f21add934df3a015e9680036d952c5d644de27","datavalue":{"value":{"entity-type":"item","numeric-id":1245976,"id":"Q1245976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185224$3EC5B3AA-EAA3-408C-BE06-FD929F84DD75","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"f834f0b0f5a2fa9641b5c8b0126fcc0b6be47d76","datavalue":{"value":"bafkreig6yuhdprth5ymiuk6345oibyqqsbir2alprqamzyiqnkc62kqf64","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185224$87F246F2-5482-4736-8B02-9990BF84D972","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54b0cb2078a9f81dc29852b9500cb6f211e5ebee","datavalue":{"value":{"entity-type":"item","numeric-id":2003768,"id":"Q2003768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a7e1556907629ab01a0aa0a0c05ebd676adb502","datavalue":{"value":{"amount":"+0.8296437859535217","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":"Q2185224$07AC1737-8E58-499F-9A27-BA51FB87FF8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2d49473fd5d258260fcfdf22f4d2d8dcfb46e66","datavalue":{"value":{"entity-type":"item","numeric-id":1410410,"id":"Q1410410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0069477b5577fc03e84b6413d2f8761f13e11c8","datavalue":{"value":{"amount":"+0.8130842447280884","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":"Q2185224$5DE7CA4E-FB4A-4D8E-8C52-C90B89753E2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c33da9cae193a068efcc82b7880e9938d0dc512d","datavalue":{"value":{"entity-type":"item","numeric-id":859617,"id":"Q859617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec2bb617646ce58374a2c50590ee1d02b066ef9c","datavalue":{"value":{"amount":"+0.8034886717796326","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":"Q2185224$7F2F1C0C-D4FB-4177-8DF0-F33F27629C23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28e9d8d560603df1bcb123d65f1b9eb154583613","datavalue":{"value":{"entity-type":"item","numeric-id":1613467,"id":"Q1613467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2d0b7343a7732560eb4c8390a78a06d8c5a4a09","datavalue":{"value":{"amount":"+0.8032466769218445","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":"Q2185224$FD2F1051-8026-4CFC-B043-F8169D82E15A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c59b7c1992698154d63b63967efc8fcafb4faeb0","datavalue":{"value":{"entity-type":"item","numeric-id":322274,"id":"Q322274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"291a123bbf57b5d0361d92d41207b5af6c2044ae","datavalue":{"value":{"amount":"+0.8012361526489258","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":"Q2185224$4AA8DF7E-B649-4FC6-8DAD-51CDEEA5471E","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":"Q2185224$FA4F5669-909C-4CAA-80CB-3B0255937B4A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2185224","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2185224"}}}}}