On the chromatic number of intersection graphs of convex sets in the plane

Seog Jin Kim, Alexandr Kostochka, Kittikorn Nakprasit

Research output: Contribution to journalArticlepeer-review

Abstract

Let G be the intersection graph of a finite family of convex sets obtained by translations of a fixed convex set in the plane. We show that every such graph with clique number k is (3k - 3)-degenerate. This bound is sharp. As a consequence, we derive that G is (3k - 2)-colorable. We show also that the chromatic number of every intersection graph H of a family of homothetic copies of a fixed convex set in the plane with clique number k is at most 6k - 6.

Original languageEnglish (US)
Pages (from-to)1-12
Number of pages12
JournalElectronic Journal of Combinatorics
Volume11
Issue number1 R
DOIs
StatePublished - Aug 19 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On the chromatic number of intersection graphs of convex sets in the plane'. Together they form a unique fingerprint.

Cite this