|
Дискретный анализ и исследование операций, сер. 1, 2001, том 8, выпуск 4, страницы 9–33
(Mi da228)
|
|
|
|
Эта публикация цитируется в 31 научных статьях (всего в 31 статьях)
Минимальные степени и хроматические числа квадратов плоских графов
О. В. Бородинa, Х. Брусмаb, А. Н. Глебовa, Я. ван ден Хойвелc a Институт математики им. С. Л. Соболева СО РАН
b University of Twente
c LSE's Centre for Discrete and Applicable Mathematics
Аннотация:
Вес предполной звезды при вершине v графа G определяется как сумма степеней
всех смежных с v вершин, кроме одной, имеющей наибольшую степень. Определены достаточные условия существования в плоском графе G предполной звезды ограниченного веса при вершине степени не более 5. Для плоских графов с максимальной степенью Δ⩾47 доказана точная верхняя оценка, равная ⌈95Δ⌉, для минимальной степени вершин квадрата G2 графа G и верхняя оценка, равная ⌈95Δ⌉+1, для его списочного хроматического числа. Получены верхние оценки для так называемых (p,q)-хроматических чисел плоских графов. Ил. 19, библиогр. 10.
Статья поступила: 02.08.2001
Образец цитирования:
О. В. Бородин, Х. Брусма, А. Н. Глебов, Я. ван ден Хойвел, “Минимальные степени и хроматические числа квадратов плоских графов”, Дискретн. анализ и исслед. опер., сер. 1, 8:4 (2001), 9–33
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da228 https://www.mathnet.ru/rus/da/v8/s1/i4/p9
|
Статистика просмотров: |
Страница аннотации: | 483 | PDF полного текста: | 260 | Список литературы: | 2 |
|