Loading [MathJax]/jax/output/CommonHTML/jax.js
Дискретный анализ и исследование операций
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретный анализ и исследование операций, сер. 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
Реферативные базы данных:
УДК: 519.172.2
Образец цитирования: О. В. Бородин, Х. Брусма, А. Н. Глебов, Я. ван ден Хойвел, “Минимальные степени и хроматические числа квадратов плоских графов”, Дискретн. анализ и исслед. опер., сер. 1, 8:4 (2001), 9–33
Цитирование в формате AMSBIB
\RBibitem{BorBroGle01}
\by О.~В.~Бородин, Х.~Брусма, А.~Н.~Глебов, Я.~ван ден Хойвел
\paper Минимальные степени и~хроматические числа квадратов плоских графов
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2001
\vol 8
\issue 4
\pages 9--33
\mathnet{http://mi.mathnet.ru/da228}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1918258}
\zmath{https://zbmath.org/?q=an:1012.05074}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da228
  • https://www.mathnet.ru/rus/da/v8/s1/i4/p9
  • Эта публикация цитируется в следующих 31 статьяx:
    1. Cranston D.W., “Acyclic Edge-Coloring of Planar Graphs: Delta Colors Suffice When Delta Is Large”, SIAM Discret. Math., 33:2 (2019), 614–628  crossref  mathscinet  zmath  isi  scopus
    2. Cranston D.W., Jaeger B., “List-Coloring the Squares of Planar Graphs Without 4-Cycles and 5-Cycles”, J. Graph Theory, 85:4 (2017), 721–737  crossref  mathscinet  zmath  isi  scopus
    3. Borodin O.V. Ivanova A.O., “New Results About the Structure of Plane Graphs: a Survey”, Proceedings of the 8th International Conference on Mathematical Modeling (ICMM-2017), AIP Conference Proceedings, 1907, ed. Egorov I. Popov S. Vabishchevich P. Antonov M. Lazarev N. Troeva M. Troeva M. Ivanova A. Grigorev Y., Amer Inst Physics, 2017, UNSP 030051  crossref  isi  scopus
    4. О. В. Бородин, А. О. Иванова, Д. В. Никифоров, “Низкие и легкие $5$-звезды в $3$-многогранниках с минимальной степенью $5$ при наличии запретов на степени старших вершин”, Сиб. матем. журн., 58:4 (2017), 771–778  mathnet  crossref  elib; O. V. Borodin, A. O. Ivanova, D. V. Nikiforov, “Low and light $5$-stars in $3$-polytopes with minimum degree $5$ and restrictions on the degrees of major vertices”, Siberian Math. J., 58:4 (2017), 600–605  crossref  isi  elib
    5. Borodin O.V., Ivanova A.O., “Low Stars in Normal Plane Maps With Minimum Degree 4 and No Adjacent 4-Vertices”, Discrete Math., 339:2 (2016), 923–930  crossref  mathscinet  zmath  isi  elib  scopus
    6. О. В. Бородин, А. О. Иванова, “Легкие и низкие $5$-звезды в нормальных плоских картах с минимальной степенью $5$”, Сиб. матем. журн., 57:3 (2016), 596–602  mathnet  crossref  mathscinet  elib; O. V. Borodin, A. O. Ivanova, “Light and low $5$-stars in normal plane maps with minimum degree $5$”, Siberian Math. J., 57:3 (2016), 470–475  crossref  isi  elib
    7. Bu Yu. Yan X., “List 2-Distance Coloring of Planar Graphs”, J. Comb. Optim., 30:4, SI (2015), 1180–1195  crossref  mathscinet  zmath  isi  elib  scopus
    8. Cranston D.W., Skrekovski R., “Sufficient Sparseness Conditions for G(2) to Be (Delta+1)-Choosable, When Delta >= 5”, Discrete Appl. Math., 162 (2014), 167–176  crossref  mathscinet  zmath  isi  elib  scopus
    9. Borodin O.V. Ivanova A.O. Jensen T.R., “5-Stars of Low Weight in Normal Plane Maps With Minimum Degree 5”, Discuss. Math. Graph Theory, 34:3 (2014), 539–546  crossref  mathscinet  zmath  isi  elib  scopus
    10. Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539  crossref  mathscinet  zmath  isi  elib  scopus
    11. Borodin O.V., Ivanova A.O., “Describing 4-Stars at 5-Vertices in Normal Plane Maps with Minimum Degree 5”, Discrete Math., 313:17 (2013), 1710–1714  crossref  mathscinet  zmath  isi  elib  scopus
    12. Amini O., Esperet L., Van den Heuvel J., “A Unified Approach to Distance-Two Colouring of Graphs on Surfaces”, Combinatorica, 33:3 (2013), 253–296  crossref  mathscinet  zmath  isi  elib  scopus
    13. Zhang X., Wang G., Yu Y., Li J., Liu G., “On R-Acyclic Edge Colorings of Planar Graphs”, Discrete Appl. Math., 160:13-14 (2012), 2048–2053  crossref  mathscinet  zmath  isi  scopus
    14. О. В. Бородин, А. О. Иванова, “Инъективная $(\Delta+1)$-раскраска плоских графов с обхватом 6”, Сиб. матем. журн., 52:1 (2011), 30–38  mathnet  mathscinet; O. V. Borodin, A. O. Ivanova, “Injective $(\Delta+1)$-coloring of planar graphs with girth 6”, Siberian Math. J., 52:1 (2011), 23–29  crossref  isi
    15. О. В. Бородин, А. О. Иванова, “2-дистанционная 4-раскраска плоских субкубических графов”, Дискретн. анализ и исслед. опер., 18:2 (2011), 18–28  mathnet  mathscinet  zmath; O. V. Borodin, A. O. Ivanova, “2-distance 4-coloring of planar subcubic graphs”, J. Appl. Industr. Math., 5:4 (2011), 535–541  crossref
    16. Borodin O.V., Ivanova A.O., “List injective colorings of planar graphs”, Discrete Math, 311:2–3 (2011), 154–165  crossref  mathscinet  zmath  isi  elib  scopus
    17. Calamoneri T., “The L(h, k)-Labelling Problem: An Updated Survey and Annotated Bibliography”, The Computer Journal, 54:8 (2011), 1344–1371  crossref  isi  scopus
    18. Иванова А.О., “2-граневая 4-раскрашиваемость плоских графов с обхватом не менее 22”, Математические заметки ЯГУ, 18:2 (2011), 52–63  zmath  elib
    19. А. О. Иванова, “Предписанная 2-дистанционная $(\Delta+1)$-раскраска плоских графов с обхватом не менее 7”, Дискретн. анализ и исслед. опер., 17:5 (2010), 22–36  mathnet  mathscinet  zmath
    20. О. В. Бородин, А. О. Иванова, “Предписанная 2–дистанционная $(\Delta+2)$-раскраска плоских графов с обхватом 6 и $\Delta\ge24$”, Сиб. матем. журн., 50:6 (2009), 1216–1224  mathnet  mathscinet; O. V. Borodin, A. O. Ivanova, “List 2-distance $(\Delta+2)$-coloring of planar graphs with girth 6 and $\Delta\ge24$”, Siberian Math. J., 50:6 (2009), 958–964  crossref  isi
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:483
    PDF полного текста:260
    Список литературы:2
     
      Обратная связь:
    math-net2025_01@mi-ras.ru
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025