A hypergraph-free construction of highly chromatic graphs without short cycles (Q915736): Difference between revisions

One of the most famous results in graph theory states that for given \(k\) and \(\ell\) there are \(k\)-chromatic graphs in which all cycles have length at least \(\ell\). This was first obtained constructively for \(\ell\leq 6\), and then in general by the non-constructive probabilistic method of \textit{P. Erdős} [Can. J. Math. 11, 34-38 (1959; Zbl 0084.39602)]. The first constructive proof was given by \textit{L. Lovász} [Theory of Graphs, Proc. Colloq. Tihany, Hungary 1966, 231-236 (1968; Zbl 0157.31202)]. The paper by Lovász and its Zbl MATH review contain detailed information on the previous result. The construction by Lovász was by induction, and it proved the result simultaneously for \(r\)-uniform hypergraphs; in fact this was an essential extension in order to make the induction work: even if one wanted the construction only for graphs, the hypergraph extension had to be done as well. The same applied to the later short construction by \textit{J. Nešetřil} and \textit{V. Rödl} [J. Comb. Theory, Ser. B 27, 225- 227 (1979; Zbl 0413.05039)]. The present proof obtains constructively the result for graphs, without getting it for hypergraphs as well. It is in this sense that the present construction is hypergraph-free, however hypergraphs are still in a sense hidden in the construction.