Том 8, серия 1, номер 4, 2001 г., Стр. 9-33
УДК 519.172.2
О. В. Бородин, Х. Брусма, А. Н. Глебов, Я. ван ден Хойвел
Минимальные степени и хроматические числа квадратов плоских графов
Аннотация:
Вес предполной звезды при вершине$v$ графа$G$ определяется как сумма степеней всех смежных с$v$ вершин, кроме одной, имеющей наибольшую степень. Определены достаточные условия существования в плоском графе$G$ предполной звезды ограниченного веса при вершине степени не более 5. Для плоских графов с максимальной степенью$\Delta\geqslant 47$ доказана точная верхняя оценка, равная$\lceil\frac95\Delta\rceil$ , для минимальной степени вершин квадрата$G^2$ графа$G$ и верхняя оценка, равная$\lceil\frac95\Delta\rceil+1$ , для его списочного хроматического числа. Получены верхние оценки для так называемых$(p,q)$ -хроматических чисел плоских графов.
Ил. 19, библиогр. 10.
Бородин О. В. 1
Брусма X. 2
Глебов А. Н. 1
ван ден Хойвел Я. 3
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. University of Twente,
Enschede, Netherlands
3. Centre for Discrete and Applicable Mathematics, Dep. of Mathematics London School of Economics,
Houghton Street, London WC2A 2AE, U. K.
е-mail: borodin@math.nsc.ru, angle@math.nsc.ru, broersma@math.utwente.nl
Статья поступила 2 августа 2001 г.
