Every circle graph of girth at least 5 is 3-colourable (Q1296984)

The girth of a graph \(G\) is the length of a shortest circuit of \(G\). A graph is a circle graph if it is isomorphic to the intersection graph of chords of a circle. It was shown in [\textit{A. V. Kostochka}, On upper bounds for the chromatic numbers of graphs, Tr. Inst. Mat. 10, 204-226 (1988; Zbl 0677.05027)] that every triangle-free (equivalently, of girth at least 4) circle graph is 5-colourable and in [\textit{A. A. Ageev}, A triangle-free circle graph with chromatic number 5, Discrete Math. 152, No. 1-3, 295-298 (1996; Zbl 0854.05049)] that there exist examples of such graphs that are not 4-colourable. In the present paper it is shown that every circle graph of girth at least 5 is 3-colourable. The main result of this paper is that every circle graph \(G\) of girth at least 5 is 2-degenerate---that is, every induced subgraph of \(G\) has a vertex of degree at most 2. From this theorem it follows that every circle graph \(G\) of girth at least 5 is 3-choosable---that is, for any assignment of size-3 colour-lists, one list \(L(v)\) for each vertex \(v\), there is a proper colouring of \(G\) which assigns to each vertex \(v\) a colour chosen from \(L(v)\). Setting \(L(v)= \{1,2,3\}\) for each vertex \(v\) implies that \(G\) is 3-colourable.