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 language | English (US) |
|---|---|
| Pages (from-to) | 1-12 |
| Number of pages | 12 |
| Journal | Electronic Journal of Combinatorics |
| Volume | 11 |
| Issue number | 1 R |
| DOIs | |
| State | Published - Aug 19 2004 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics