A triangle-free circle graph with chromatic number 5 (Q1917502): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q166312 |
||
Property / reviewed by | |||
Property / reviewed by: Martin Škoviera / rank | |||
Revision as of 03:02, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A triangle-free circle graph with chromatic number 5 |
scientific article |
Statements
A triangle-free circle graph with chromatic number 5 (English)
0 references
13 January 1997
0 references
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.
0 references
circle graph
0 references
chords
0 references
chromatic number
0 references