Induced subgraphs of graphs with large chromatic number. III: Long holes (Q722311): Difference between revisions

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árfás} [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)].