A triangle-free circle graph with chromatic number 5
type: Item
instance of: scholarly article
title: A triangle-free circle graph with chromatic number 5
zbMATH Open document ID: 0854.05049
DOI: 10.1016/0012-365X(95)00349-2
author: Alexander Ageev
published in: Discrete Mathematics
publication date: 1997-01-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 897585
zbMATH Keywords: circle graph
zbMATH Keywords: chords
zbMATH Keywords: chromatic number
reviewed by: Martin Škoviera
MaRDI profile type: Publication
Wikidata QID: Q55954533
cites work: On the chromatic number of multiple interval graphs and overlap graphs
cites work: Covering and coloring problems for relatives of intervals
cites work: 25 pretty graph colouring problems
cites work: Q3832590
cites work: Covering and coloring polygon-circle graphs
cites work: Q3715043
description: scientific article; zbMATH DE number 897585