|
This article is cited in 2 scientific papers (total 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.
Received: 07.04.1999
Citation:
R. N. Shmatkov, “On Coloring Polygon-Circle Graphs with Clique Number 2”, Mat. Tr., 3:1 (2000), 197–211; Siberian Adv. Math., 10:1 (2000), 73–86
Linking options:
https://www.mathnet.ru/eng/mt164 https://www.mathnet.ru/eng/mt/v3/i1/p197
|
Statistics & downloads: |
Abstract page: | 235 | Full-text PDF : | 76 | First page: | 1 |
|