On Coloring Polygon-Circle Graphs with Clique Number~2

R. N. Shmatkov

Matematičeskie trudy, Tome 3 (2000) no. 1, pp. 197-211.

Résumé

In his paper (see [1]) A. V. Kostochka proved that the maximum of chromatic numbers of circle graphs (intersection graphs of chords inscribed in a circle) with clique number 2 is at most 5. A. A. Ageev established in 1995 (see [2]) that the maximum of chromatic numbers of this class of graphs is at least 5. So, he proved that the upper bound obtained by A. V. Kostochka is the best possible. From the above-mentioned results of A. A. Ageev it follows that $\chi (G)\ge 5$, where $\chi (G)$ is the maximum of chromatic numbers of all polygon-circle graphs (intersection graphs of (convex) polygons inscribed in a circle) with clique number 2. In this article we prove that $\chi (G)\le 5$ and, thus, $\chi (G)=5$.