"Записки научных семинаров ПОМИ"
Том 450 , стр. 5-13
О связи между хроматическим числом графа и количеством циклов, покрывающих данное ребро или вершину
С. Л. Берлов, К. И. Тыщук
Физико-математический лицей No. 239,
ул. Кирочная д.8а,
191028, Санкт-Петербург, Россия
sberlov@rambler.ru
- Аннотация:
В работе доказываются точные оценки хроматического числа графа в
зависимости от минимального количества простых циклов, проходящих
через ребро графа: если через любое ребро графа $G$ проходит менее
$[e(k-1)!-1]$ простых циклов, то $\chi(G)\leq k$. Если через любую
вершину графа $G$ проходит менее $[{ek!\over 2} - {k+1\over 2}]$
простых циклов, то $\chi(G)\leq k$. Также получены точные оценки на
количество циклов, покрывающих ребро или вершину $k$-критического
графа.
Библ. -- 7 назв.
- Ключевые слова: правильная раскраска, хроматическое число
[ proper coloring, chromatic number]
Полный текст(.pdf)