RUS  ENG
Full version
JOURNALS // Matematicheskie Trudy // Archive

Mat. Tr., 2000 Volume 3, Number 1, Pages 197–211 (Mi mt164)

This article is cited in 2 papers

On Coloring Polygon-Circle Graphs with Clique Number 2

R. N. Shmatkov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: 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$.

Key words: clique number, chromatic number, coloring, polygon-circle graph.

UDC: 517.90

Received: 07.04.1999


 English version:
Siberian Advances in Mathematics, 2000, 10:1, 73–86

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024