dc.contributor.editor | Díaz Báñez, José Miguel | es |
dc.contributor.editor | Garijo Royo, Delia | es |
dc.contributor.editor | Márquez Pérez, Alberto | es |
dc.contributor.editor | Urrutia Galicia, Jorge | es |
dc.creator | Cibulka, Josef | es |
dc.creator | Korbelář, Miroslav | es |
dc.creator | Kynčl, Jan | es |
dc.creator | Mészáros, Viola | es |
dc.creator | Stolař, Rudolf | es |
dc.creator | Valtr, Pavel | es |
dc.date.accessioned | 2017-05-23T06:18:24Z | |
dc.date.available | 2017-05-23T06:18:24Z | |
dc.date.issued | 2013 | |
dc.identifier.citation | 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. | |
dc.identifier.uri | http://hdl.handle.net/11441/60268 | |
dc.description.abstract | 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. | es |
dc.description.sponsorship | Czech Science Foundation | es |
dc.description.sponsorship | Ministry of Education, Youth and Sports of the Czech Republic | es |
dc.description.sponsorship | European Science Foundation | es |
dc.description.sponsorship | Országos Tudományos Kutatási Alapprogramok (OTKA) | es |
dc.description.sponsorship | Centre Interfacultaire Bernoulli | es |
dc.description.sponsorship | Swiss National Science Foundation | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.relation.ispartof | XV Spanish Meeting on Computational Geometry (2013), pp. 111-114. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | On three parameters of invisibility graphs | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada II | |
dc.relation.projectID | GACR P202/12/G061 | es |
dc.relation.projectID | SVV-2013-267313 | es |
dc.relation.projectID | CZ.1.07/2.3.00/20.0003 | es |
dc.relation.projectID | K76099 | es |
dc.relation.projectID | 102029 | es |
dc.relation.projectID | GAUK 52410 | es |
dc.relation.publisherversion | http://congreso.us.es/ecgeometry/proceedingsECG2013.pdf | es |
idus.format.extent | 4 p. | es |
dc.publication.initialPage | 111 | es |
dc.publication.endPage | 114 | es |
dc.eventtitle | XV Spanish Meeting on Computational Geometry | es |
dc.eventinstitution | Sevilla | es |