Coloring circle graphs期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Coloring circle graphs

Institution:	1. University of Kaiserslautern (Department of Mathematics), Kaiserslautern, Germany;2. Université Blaise Pascal (Clermont-Ferrand II, LIMOS), BP 10125, 63173 Aubière Cedex, France;1. Departamento de Computação, Universidade Federal do Ceará, Fortaleza, Brazil;1. University of Warwick, Coventry, UK;2. University of Sheffield, Sheffield, UK;1. Department of Mathematics, Zhejiang Normal University, Jinhua, Zhejiang, China;2. Center for Discrete Mathematics, Fuzhou University, Fuzhou, Fujian, China

Abstract:	Circle graph is an intersection graph of chords of a circle. We denote the class of circle graphs by cir. In this paper we investigate the chromatic number of the circle graph as a function of the size of maximum clique $ω = ω (G)$ . More precisely we investigate $f (k) = \max {χ (G) \| G \in CIR & ω (G) ⩽ k}$ . Kratochvíl and Kostochka showed that $f (k) ⩽ 50 \cdot 2^{k} - 32 k - 64$ . The best lower bound is by Kostochka and is $f (k) = Ω (k \log k)$ . We improve the upper bound to $f (k) ⩽ 21 \cdot 2^{k} - 24 k - 24$ . We also present the bound $χ (G) ⩽ ω \cdot \log n$ which shows, that the circle graphs with small maximum clique and large chromatic number must have many vertices.

Keywords:
本文献已被 ScienceDirect 等数据库收录！