Ponencia
On three parameters of invisibility graphs
Autor/es | Cibulka, Josef
Korbelář, Miroslav Kynčl, Jan Mészáros, Viola Stolař, Rudolf Valtr, Pavel |
Coordinador/Director | Díaz Báñez, José Miguel
Garijo Royo, Delia Márquez Pérez, Alberto Urrutia Galicia, Jorge |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada II |
Fecha de publicación | 2013 |
Fecha de depósito | 2017-05-23 |
Publicado en |
|
Resumen | The invisibility graph I(X) of a set X ⊆ Rd is a (possibly infinite) graph whose vertices are the points of X and two vertices are connected by an edge if and
only if the straight-line segment connecting the two corresponding ... The invisibility graph I(X) of a set X ⊆ Rd is a (possibly infinite) graph whose vertices are the points of X and two vertices are connected by an edge if and only if the straight-line segment connecting the two corresponding points is not fully contained in X . We consider the following three parameters of a set X : the clique number ω(I(X)), the chromatic number χ(I(X)) and the inimum number γ(X) of convex subsets of X that cover X. We settle a conjecture of Matousek and Valtr claiming that for every planar set X, γ(X) can be bounded in terms of χ(I(X)). As a part of the proof we show that a disc with n one-point holes near its boundary has χ(I(X)) ≥ log log(n) but ω(I(X)) = 3. We also find sets X in R5 with χ(I(X)) = 2, but γ(X) arbitrarily large. |
Identificador del proyecto | GACR P202/12/G061
SVV-2013-267313 CZ.1.07/2.3.00/20.0003 K76099 102029 GAUK 52410 |
Cita | Cibulka, J., Korbelář, M., Kynčl, J., Mészáros, V., Stolař, R. y Valtr, P. (2013). On three parameters of invisibility graphs. En XV Spanish Meeting on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
On three parameters of invisibility ... | 663.6Kb | [PDF] | Ver/ | |