Том 9, серия 1, номер 2 , 2002 г., Стр. 3-20

УДК 519.17
А. Н. Глебов
Оценки для числа вырожденности графов пересечений боксов на плоскости в зависимости от обхвата

Аннотация:
Боксом на плоскости с заданной прямоугольной системой координат называется прямоугольник, стороны которого параллельны координатным осям. $B$-граф определяется как граф пересечений произвольного семейства боксов. Доказано, что всякий $B$-граф с обхватом не менее 5 является 5-вырожденным и предписанно 5-раскрашиваемым. Приводятся примеры $B$-графов с обхватом 5 и минимальной степенью 4 и с обхватом 7 и минимальной степенью 3. Первый пример говорит о неулучшаемости доказанной верхней оценки для числа вырожденности $B$-графов с обхватом не менее 5. Оба примера доказывают неулучшаемость известных оценок, согласно которым $B$-графы с обхватом не менее 6 (соответственно 8) являются 4(3)-вырожденными.
Ил. 9, библиогр. 4.

Глебов А. Н. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: angle@math.nsc.ru

Статья поступила 15 февраля 2002 г.