A triangle-free circle graph with chromatic number 5 (Q1917502): Difference between revisions

A circle graph is a graph isomorphic to the intersection graph of chords of a circle. The chromatic number of a circle graph may be arbitrarily large. Let \(\chi^*\) denote the maximum value of \(\chi(G)\) where \(G\) is a triangle-free circle graph. \textit{A. Gyárfás} and \textit{J. Lehel} [Discrete Math. 55, 167-180 (1985; Zbl 0569.05020)] and \textit{Karapetyan} [Ph.D. thesis, Novosibirsk, 1984] proved that \(\chi^*\geq 4\). On the other hand, \textit{A. V. Kostochka} [Tr. Inst. Mat. 10, 204-226 (1988; Zbl 0677.05027)] showed that \(\chi^*\leq 5\). In this paper an example establishing \(\chi^*= 5\) is given.