Аннотация:
В этом докладе будет рассказано о раскраске геометрических графов и
гиперграфов, обладающих $(p,q)$-свойством.
Понятие $(p,q)$-свойства первоначально было введено Хадвигером и
Дебруннером для семейства вынуклых тел в $\mathbb R^d$ в связи с
обобщением теоремы Хелли.
Пусть $G=(V,E)$ это гиперграф, а $p$, $q$ целые числа такие, что
$p\geqslant q\geqslant 1$. Будем говорить, что $G$ имеет
$(p,q)$-свойство, если $|V|\geqslant p$, а каждое подмножество $V'\subseteq V$ с $|V|\geqslant p$ содержит независимое подмножество из
$q$ элементов.
Следующая теорема это основной новый результат этого доклада.
Теорема. Пусть числа $r$, $p$, $q$, $p\geqslant
q\geqslant r$ натуральные и $d=p-q$.
Если $p<r(d+1)$, то для всех $N$ существует $r$-граф $G$, имеющий
$(p,q)$-свойство такой, что $\chi(G)>N$.
Если $p\geqslant r(d+1)$, то для любого $r$-графа $G$, имеющего
$(p,q)$-свойство выполняются неравенства
$$
\left\lceil\frac{d}{r-1}\right\rceil+1 \le \chi(G)
\leqslant\left\lceil \frac {d}{r-1} \right\rceil + 2.
$$
|
