Charles Explorer logo
🇨🇿

O barevnosti viditelnostních grafů

Publikace |
2005

Abstrakt

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.