Charles Explorer logo
🇨🇿

O třech parametrech neviditelnostních grafů

Publikace na Matematicko-fyzikální fakulta |
2010

Abstrakt

Neviditelnostní graf I(X) množiny X v euklidovském prostoru je (typicky nekonečný) graf, jehož vrcholy jsou body X a dva vrcholy jsou spojeny hranou právě tehdy, když úsečka, která je spojuje, není celá obsažena v X. Dokážeme domněnku Matouška a Valtra, která tvrdí, že barevnost neviditelnostních grafů rovinných množin není omezena funkcí klikovosti.