Geodesic
On the chromatic number of intersection graphs of convex sets in the plane
The electronic journal of combinatorics, Tome 11 (2004) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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$.
DOI : 10.37236/1805
Classification : 05C15, 05C35
Mots-clés : intersection graph, convex sets, clique number, chromatic number 
@article{10_37236_1805,
     author = {Seog-Jin Kim and Alexandr Kostochka and Kittikorn Nakprasit},
     title = {On the chromatic number of intersection graphs of convex sets in the plane},
     journal = {The electronic journal of combinatorics},
     year = {2004},
     volume = {11},
     number = {1},
     doi = {10.37236/1805},
     zbl = {1054.05040},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1805/}
}
TY  - JOUR
AU  - Seog-Jin Kim
AU  - Alexandr Kostochka
AU  - Kittikorn Nakprasit
TI  - On the chromatic number of intersection graphs of convex sets in the plane
JO  - The electronic journal of combinatorics
PY  - 2004
VL  - 11
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1805/
DO  - 10.37236/1805
ID  - 10_37236_1805
ER  - 
%0 Journal Article
%A Seog-Jin Kim
%A Alexandr Kostochka
%A Kittikorn Nakprasit
%T On the chromatic number of intersection graphs of convex sets in the plane
%J The electronic journal of combinatorics
%D 2004
%V 11
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1805/
%R 10.37236/1805
%F 10_37236_1805
Seog-Jin Kim; Alexandr Kostochka; Kittikorn Nakprasit. On the chromatic number of intersection graphs of convex sets in the plane. The electronic journal of combinatorics, Tome 11 (2004) no. 1. doi: 10.37236/1805

Cité par Sources :