On the Chromatic Number of the Visibility Graph of a Set of Points in the Plane

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F05%3A00005597" target="_blank" >RIV/00216208:11320/05:00005597 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
On the Chromatic Number of the Visibility Graph of a Set of Points in the Plane
Original language description
The visibility graph $V(P)$ of a set of points $P$ in the plane is the graph with vertex set $P$ where two vertices $u$ and $v$ are adjacent if and only if there is no point from $P$ on the segment connecting $u$ with $v$. We study the chromatic number of $V(P)$ and show superpolynomial lower bound on the chromatic number in terms of clique number.
Czech name
O barevnosti viditelnostních grafů
Czech description
Viditelnostní graf $V(P)$ množiny bodů v rovině $P$ je graf s vrcholy $P$, kde vrcholy $u$ a $v$ jsou spojené hranou právě když na úsečce spojující $u$ a $v$ neleží žádný jiný bod z $P$. V práci studujeme barevnost $V(P)$ a ukážeme super-polynomiální dolní mez na barevnost vzhledem ke klikovosti.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/LN00A056" target="_blank" >LN00A056: Institute of Theoretical Computer Science (Center of Young Science)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2005
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)