{"entities":{"Q2034076":{"pageid":2044818,"ns":120,"title":"Item:Q2034076","lastrevid":72471444,"modified":"2026-04-14T05:08:49Z","type":"item","id":"Q2034076","labels":{"en":{"language":"en","value":"Structure and colour in triangle-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7361305"}},"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":"Q2034076$EB94982E-CF23-4526-96AF-6C00B8FD700E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ce98b24f0296ea6d75c5c4b0e8b2ff7717dd44e9","datavalue":{"value":{"text":"Structure and colour in triangle-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2034076$F9185E23-274B-4A93-BC48-D927C2F402BA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"221f8abfe7c9bc53bfb3972ff9417467882bb65d","datavalue":{"value":"1466.05063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2034076$8001E536-3A03-43A1-8685-B775369E1F77","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6b763d9002e3509436c38dd753db1791368f2c5c","datavalue":{"value":"10.37236/9267","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2034076$DD70887F-AA04-493D-88CF-A8D8C98FDBC8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6db2457b24414fcbed0f80e611570bf20ca2ecee","datavalue":{"value":{"entity-type":"item","numeric-id":536212,"id":"Q536212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$071719D5-932F-425F-8B32-81271EBC375E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"97339d72ec7b011009b86d674b67c005a477bbd7","datavalue":{"value":{"entity-type":"item","numeric-id":820841,"id":"Q820841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$62F3CEFB-1AEC-413C-8303-4BCCF7298E6D","rank":"normal"},{"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":"Q2034076$867D453B-6BEE-481C-8F9E-E1382F59ECA6","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":"Q2034076$4A10A764-7B8C-4E83-A770-328968C45AC3","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":"Q2034076$EA88CDB3-4903-4719-81F8-98F00DB7C9A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d42222c166d248cb8fb92648a8a738de86662abf","datavalue":{"value":{"entity-type":"item","numeric-id":309790,"id":"Q309790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$43F28A0E-8EEA-4D63-8F79-2FC49921D6F9","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":"Q2034076$EF1449F3-A621-4443-A24E-8BC6C330D373","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d2f3a985dcf2407d30ab45f57448460afb353a2a","datavalue":{"value":{"time":"+2021-06-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2034076$0DE3E9C5-E8F0-455F-AAA5-FE1BDF302995","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cd40d105fc3d67383d6f6730fe7e96746e0e3cfe","datavalue":{"value":"https://arxiv.org/abs/1912.13328","type":"string"},"datatype":"url"},"type":"statement","id":"Q2034076$DC2DFCCD-BD3D-4A87-894E-EE3D504C3481","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c9ef53113dd78d87d84b9fdd1019a383c5f425d1","datavalue":{"value":"Summary: Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number \\(\\chi\\) contains a rainbow independent set of size \\(\\lceil\\frac12\\chi\\rceil \\). This is sharp up to a factor 2. This result and its short proof have implications for the related notion of chromatic discrepancy.  Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number \\(\\chi\\) contains an induced cycle of length \\(\\Omega(\\chi\\log\\chi)\\) as \\(\\chi\\to\\infty \\). Even if one only demands an induced path of length \\(\\Omega(\\chi\\log\\chi)\\), the conclusion would be sharp up to a constant multiple. We prove it for regular girth 5 graphs and for girth 21 graphs.  As a common strengthening of the induced paths form of this conjecture and of \\textit{A. Johansson}'s theorem [Asymptotic choice number for triangle-free graphs. Techn. Rep. 91-5, DIMACS (1996)], we posit the existence of some \\(c >0\\) such that for every forest \\(H\\) on \\(D\\) vertices, every triangle-free and induced \\(H\\)-free graph has chromatic number at most \\(c D/\\log D\\). We prove this assertion with `triangle-free' replaced by `regular girth 5'.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2034076$6BFD1181-E074-4970-A729-01610F8F33C9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2034076$7C1A494F-0B87-4F88-8F82-C5340D3C44D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2034076$CF6FC324-BAD4-4702-800B-9224581116B5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c50958f670b16828c8f39da8087a784ba8cc73e6","datavalue":{"value":"7361305","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2034076$E274BEBB-483F-4A12-A669-BD72682D6C16","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34249a0faab9cbfce87f98ed0aeac67f27fb4445","datavalue":{"value":"Johansson's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2034076$53E3C18D-FB7D-4557-8D2F-75C5E60F1D48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2034076$CB8AF9B9-E4E3-4DB3-ABE7-E8C32544247B","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":"Q2034076$E04D3530-3B30-4EC6-BDEC-3E7E725138EA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cb3efd6857240aa8c6f79cef69927ead89bd429c","datavalue":{"value":"W3174897553","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2034076$785B69FE-563A-4724-9023-9C08DCD36556","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":"Q2034076$A937B939-04A8-4F10-941C-14EBDCCD65C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92a8b03722c2c44cdc28b3e047af5bf4cd35a4e9","datavalue":{"value":{"entity-type":"item","numeric-id":1569053,"id":"Q1569053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$EBA2CCB3-7C64-4A60-A502-CEA8B8904AAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e86718df3600b77443894cb71ef57e47b183534","datavalue":{"value":{"entity-type":"item","numeric-id":2341751,"id":"Q2341751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$346F8D1C-4A37-4817-9E1E-76F63A38BF07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b727335b4f2906d42e54f4781565f646223f43fb","datavalue":{"value":{"entity-type":"item","numeric-id":982189,"id":"Q982189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$8BADF081-E37B-48BF-A77A-A4C5E65D1E50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad3826adb189946c1939f59b2c74f27caa4850a0","datavalue":{"value":{"entity-type":"item","numeric-id":722311,"id":"Q722311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$59093797-EE52-49D7-BFFF-CD5C6C6C2BF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bdd250a45275500c245c98aa669a4cad3fe76cd","datavalue":{"value":{"entity-type":"item","numeric-id":5545303,"id":"Q5545303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$5B2D62B2-8A53-4FC8-91DA-A126F26DC035","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b8b57677a0d06c6630de1f95258ead75ed89053","datavalue":{"value":{"entity-type":"item","numeric-id":4063176,"id":"Q4063176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$D8B07565-9AD4-41B8-8378-F6BA1DB97A69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecea865227114740eed2d5859f102d9f3a0ca075","datavalue":{"value":{"entity-type":"item","numeric-id":5749319,"id":"Q5749319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$09F5EF66-08EA-451F-BE5B-F756D1BA00DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6c1243527c538ffa2794f311b50b82b3217e829","datavalue":{"value":{"entity-type":"item","numeric-id":504985,"id":"Q504985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$A43CF112-C626-4877-BFCF-19631A3B0224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab1681720f15f93e180f2626e5ed0fb1f9e0ce5e","datavalue":{"value":{"entity-type":"item","numeric-id":1159679,"id":"Q1159679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$4444B316-ED55-468D-951C-FED0FA1E6278","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c21b97a1c274a5f75c018b79e9170da70257e50a","datavalue":{"value":{"entity-type":"item","numeric-id":5617553,"id":"Q5617553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$8D2DE5BD-8471-430A-AA94-5DFF204B0752","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":"Q2034076$2D6BDF8C-EA8E-4E08-BCCF-2F82E19DD2FD","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":"Q2034076$D7D7BC52-B883-493F-BEC8-4A926417E406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fab1b373895793d37ed441d8b74ec9c2d1774b9","datavalue":{"value":{"entity-type":"item","numeric-id":1197025,"id":"Q1197025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$FC28C678-6167-4101-9EA8-DEE536E9498C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc9d0fb35664d596a28ec73c5cf6274eaa1b799b","datavalue":{"value":{"entity-type":"item","numeric-id":4800396,"id":"Q4800396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$7C694910-7608-4C3A-B3A6-C07362902739","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c810b8a19ba478918f72aa9b6c21e780e89601d6","datavalue":{"value":{"entity-type":"item","numeric-id":1210559,"id":"Q1210559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$3907F3BB-A9E1-48CE-98A3-4E2441275584","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58f880285370162a5686ef76a9b220a32fb8498a","datavalue":{"value":{"entity-type":"item","numeric-id":5434248,"id":"Q5434248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$D18CD057-D0E7-450B-8D99-9FBEEB7DB996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70b64c36f147f07e9132a04121c3023f0fae5bd8","datavalue":{"value":{"entity-type":"item","numeric-id":5539654,"id":"Q5539654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$FBE7B9AE-07FB-4728-8903-B7550AF6EEFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a956413e2230b88f3907aaf7fe81a5b4c34092c0","datavalue":{"value":{"entity-type":"item","numeric-id":2363116,"id":"Q2363116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$06F7A300-DA5A-4182-AEC8-35F815356D25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55e23009c798e010c5ab1ffddc09b137bd888dcb","datavalue":{"value":{"entity-type":"item","numeric-id":723885,"id":"Q723885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$EDF8E280-6B8B-4C68-9630-BA8563E674F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f21894fa003250cbee384587bf63998367f6c4af","datavalue":{"value":{"entity-type":"item","numeric-id":5066934,"id":"Q5066934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$25A7F4D2-B5FE-4A27-923D-66138C4FF92A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5dd0fecefa4e12c886e333fa0a2045715c1cf19d","datavalue":{"value":{"entity-type":"item","numeric-id":1095149,"id":"Q1095149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$F19F79B0-A702-41F7-AC21-C9F1E06F9B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38a1643a3f55fd10ed31ef36d7cba0e5d3b84f16","datavalue":{"value":{"entity-type":"item","numeric-id":3932997,"id":"Q3932997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$11C4BDD0-EEE0-4986-AB5F-F99CB4C2F0C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c9d5f997ad4e98faf4457159b52d629b48df3f6","datavalue":{"value":{"entity-type":"item","numeric-id":5331780,"id":"Q5331780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2034076$B1E39252-14F5-4107-B3F9-5BF2BE47C682","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"59d36a041b3db4b2e11508d15b36346c6b14908e","datavalue":{"value":"bafkreifj6und6hemnmzuxkxdwhtkno7jrqhuyacdpxcj2h46l7zzln5dxi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2034076$DAD65A8D-DC86-458C-BDC2-85D77673F384","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8285b69418a04689ed545130dad98507935fdb6a","datavalue":{"value":{"entity-type":"item","numeric-id":1743172,"id":"Q1743172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79e7519e4771a2705ec87ef7681c6844827e1b14","datavalue":{"value":{"amount":"+0.8390544056892395","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":"Q2034076$C694ECCE-867C-4529-A611-119EDBE1A585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fb0d9d5ecda789a252e43716304d3047c06881c","datavalue":{"value":{"entity-type":"item","numeric-id":504985,"id":"Q504985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1f895a408efeccabc03adbd2b6b3d27308c1436","datavalue":{"value":{"amount":"+0.8255846500396729","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":"Q2034076$987A30C5-FFDE-464F-B42C-79E1FC2F93F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61db5c1392dc795c197c7c1b768c95b9a045bf63","datavalue":{"value":{"entity-type":"item","numeric-id":1969797,"id":"Q1969797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ae333f41185af881a00eadfeefa227a09078b61","datavalue":{"value":{"amount":"+0.8198185563087463","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":"Q2034076$5486D9E8-71A3-40B8-88AE-4D91DF158F7D","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":"Q2034076$2F8919B2-B5DA-4800-9668-4B1EEF72CA78","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Structure and colour in triangle-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Structure_and_colour_in_triangle-free_graphs"}}}}}