On the chromatic number of intersection graphs of convex sets in the plane (Q1883668)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the chromatic number of intersection graphs of convex sets in the plane |
scientific article; zbMATH DE number 2107494
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the chromatic number of intersection graphs of convex sets in the plane |
scientific article; zbMATH DE number 2107494 |
Statements
On the chromatic number of intersection graphs of convex sets in the plane (English)
0 references
13 October 2004
0 references
Summary: 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\).
0 references
intersection graph
0 references
convex sets
0 references
clique number
0 references
chromatic number
0 references
