Let the vertices of a circle graph be divided into several groups. This paper contains lower bounds on the size of an independent set that can be contained in one group of this subdivision. Bibliography: 7 titles.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
F. Gavril, “Algorithms for a maximum clique and a maximum independent set of a circle graph,” Networks, 3, 261–273 (1975).
H. de Fraysseix, “A characterization of circle graphs,” Europ. J. Combinatorics, 5, 223–238 (1984).
A. V. Kostochka and J. Kratochvil, “Covering and coloring polygon-circle graphs,” Disc. Math., 163, 299–305 (1997).
A. V. Kostochka, “On upper bounds for the chromatic numbers of graphs,” Trudy Inst. Math., 10, 204–226 (1988).
A. A. Ageev. “A triangle-free circle graph with chromatic number 5,” Disc. Math., 152, Nos. 1–3, 295–298 (1996).
G. V. Nenashev, “An upper bound on the chromatic number of circle graphs without K 4,” Zap. Nauchn. Semin. POMI, 391, 149–156 (2011).
V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, and R. I. Tyshkevich, Lectures in Graph Theory [in Russian], Nauka, Moscow (1990).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 417, 2013, pp. 5–10.
Rights and permissions
About this article
Cite this article
Berlov, S.L. Independent Sets and Chromatic Numbers of Circle Graphs. J Math Sci 204, 181–184 (2015). https://doi.org/10.1007/s10958-014-2196-1
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-014-2196-1