{"entities":{"Q722311":{"pageid":724160,"ns":120,"title":"Item:Q722311","lastrevid":63876093,"modified":"2026-04-11T16:08:33Z","type":"item","id":"Q722311","labels":{"en":{"language":"en","value":"Induced subgraphs of graphs with large chromatic number. III: Long holes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6909474"}},"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":"Q722311$7729BB92-D0E3-4A54-9E36-BDF6CDF96B9F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ecdfdddeb982d14d01d8d3da54fbc0ed7ae43bc7","datavalue":{"value":{"text":"Induced subgraphs of graphs with large chromatic number. III: Long holes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q722311$6D376C8A-E05E-456A-8A3C-ADCC9673EF66","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bfac541f7818f2b36d44e3a095c33ebf3157a37c","datavalue":{"value":"1399.05068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q722311$83BBAAE5-138C-4D60-82B2-1889369D507E","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":"Q722311$10FB3988-5317-49A3-9455-D7E7FE5951ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c70c86fdd9ac2f3762d68b8ab433b6fded65cc2e","datavalue":{"value":{"entity-type":"item","numeric-id":722310,"id":"Q722310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722311$91A8F563-823F-40FE-A361-9F7AD90F4E20","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":"Q722311$2C7CF83A-3588-4CAC-9377-5418C2098927","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":"Q722311$DE676917-C4BE-4650-980F-EF92891F7D64","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fc8ead1e0a28b70e88525b0ff5541d1c12dd7ebc","datavalue":{"value":{"time":"+2018-07-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q722311$496E997C-7CDD-4077-B695-E620545D35D5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a5dd1f198e58eb9497d14afbab84d9c7c870e25b","datavalue":{"value":"https://arxiv.org/abs/1506.02232","type":"string"},"datatype":"url"},"type":"statement","id":"Q722311$BE6B8C99-71E7-48BC-853B-1A32FF9CAE87","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b1e1ececec44c300003851609141632881c6e728","datavalue":{"value":"This paper is structured into five sections. In Section 1, the notations of a hole in a graph \\(G\\), the length \\(l\\) of a path or cycle and three well-known conjectures of \\textit{A. Gy\u00e1rf\u00e1s} [Zastosow. Mat. 19, No. 3--4, 413--441 (1987; Zbl 0718.05041)] are presented. The main result of this paper is the proof of the second conjecture of Gyarfas: for all integers \\(k, l > 0\\) there exists \\(c\\) such that every graph \\(G\\) with no clique of cardinality large than \\(k\\) and no hole of length large than \\(L\\) has chromatic number at most \\(c\\). In Section 2 the multicovers problem is presented. The goal of Sections 3 is to introduce some terminology, to describe precisely the results after the clean-up process (but before the application of Ramsey's theorem) and then to carry out the application of Ramsey's theorem. The authors explain the clean-up process that they plan to apply to the long sequence of covers. In Section 4 and in Section 5, the proof of the main theorem and the proof of the second conjecture of Gyarfas are presented.    For Part II and Part I see [the authors, J. Comb. Theory, Ser. B 118, 109--128 (2016; Zbl 1332.05053); the second and the third author, ibid. 121, 68--84 (2016; Zbl 1412.05076)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q722311$FBA75C63-49AB-4D56-9DDC-33BF206404F4","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":"Q722311$475BE73E-D647-4842-B210-AA34A8AD294B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q722311$A065E79B-C5C9-43B8-A83F-BA4DDB4066CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q722311$C7C1FE3F-4D4A-488C-AF66-F276179114D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q722311$48B396AA-6DFA-4279-9D3F-2D4DA7662C7D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3f39ff3785eca3935143564293dd48bba7a674ce","datavalue":{"value":"6909474","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q722311$D784A8AE-AB4C-4C9A-AFAD-283A11B6E18D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q722311$9B7229E6-7553-4624-AB19-C38D98938EA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f4bc5ef64b80473f2dd853aa845c54c1eb0ce36","datavalue":{"value":"induced subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q722311$13965E12-8B90-4A25-B72C-F16DCA118D92","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":"Q722311$92E087D9-DDE2-4636-A8AA-6447B83E31BB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f4c21865161b283cd185f05ca086ef69a18c05a7","datavalue":{"value":"W2964147791","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q722311$5555466B-7291-47D3-BBE5-B25A549F6CFA","rank":"normal"}],"P223":[{"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":"Q722311$D2AC1151-BFA5-4E2B-9818-1D641A3D2621","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93235389489d4985c22c8f9eedce8e4bc072b691","datavalue":{"value":{"entity-type":"item","numeric-id":326809,"id":"Q326809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722311$F40BA224-B09A-46C3-9B52-1E8C2B7CB2B2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a10f27b42fa11919142143b8dd45258a57cc8b33","datavalue":{"value":"10.1007/S00493-016-3467-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q722311$DA8BD973-1BFC-446A-9822-7A7828822B07","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e650165c34558716d5fdaaf60eaa443df0c49abf","datavalue":{"value":{"entity-type":"item","numeric-id":2284726,"id":"Q2284726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4817df6c59c79f151465d8848b0d1cc77c18e8a5","datavalue":{"value":{"amount":"+0.8839634656906128","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":"Q722311$BEA8AFBA-4FF3-48A1-B6D6-36BFAD84A3BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f27b7c8ea353a079bf7db417c4268a9b99a0c217","datavalue":{"value":{"entity-type":"item","numeric-id":5066934,"id":"Q5066934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"62a3a18cc92bae85c11f02831a718261a1ecdb00","datavalue":{"value":{"amount":"+0.8795928955078125","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":"Q722311$2B1D19E1-662E-403D-B88D-33907C37B9BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbfb10db1ffcf278c67c314deaebbe73040b865e","datavalue":{"value":{"entity-type":"item","numeric-id":256991,"id":"Q256991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b16f14d43e2c8abe25c8929013e14e9848f287a","datavalue":{"value":{"amount":"+0.8738350868225098","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":"Q722311$7DB7CB12-1FE9-45AB-A884-A74AF092A064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8acebb7e00ce738cd41668eb00dfe30daf789147","datavalue":{"value":{"entity-type":"item","numeric-id":326809,"id":"Q326809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f5f75f108800200b76137cbab84661b03007587","datavalue":{"value":{"amount":"+0.8521733283996582","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":"Q722311$5836BF15-BE66-4738-9949-201E34E3ACAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2981722de0ec04f9298aca2d094a6c1015922e4","datavalue":{"value":{"entity-type":"item","numeric-id":1985444,"id":"Q1985444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4018544c373f68284c3e71cb3ee0d092a3e2134","datavalue":{"value":{"amount":"+0.8473286628723145","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":"Q722311$A6DFA98E-86F2-4901-A383-A7AAB4F91D75","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Induced subgraphs of graphs with large chromatic number. III: Long holes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Induced_subgraphs_of_graphs_with_large_chromatic_number._III:_Long_holes"}}}}}