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

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

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



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






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


Дискретн. анализ и исслед. опер., сер. 1, 2001, том 8, номер 4, страницы 9–33 (Mi da228)  

Эта публикация цитируется в 30 научных статьях (всего в 30 статьях)

Минимальные степени и хроматические числа квадратов плоских графов

О. В. Бородинa, Х. Брусмаb, А. Н. Глебовa, Я. ван ден Хойвелc

a Институт математики им. С. Л. Соболева СО РАН
b University of Twente
c LSE's Centre for Discrete and Applicable Mathematics

Аннотация: Вес предполной звезды при вершине $v$ графа $G$ определяется как сумма степеней всех смежных с $v$ вершин, кроме одной, имеющей наибольшую степень. Определены достаточные условия существования в плоском графе $G$ предполной звезды ограниченного веса при вершине степени не более 5. Для плоских графов с максимальной степенью $\Delta\geqslant 47$ доказана точная верхняя оценка, равная $\lceil\frac95\Delta\rceil$, для минимальной степени вершин квадрата $G^2$ графа $G$ и верхняя оценка, равная $\lceil\frac95\Delta\rceil+1$, для его списочного хроматического числа. Получены верхние оценки для так называемых $(p,q)$-хроматических чисел плоских графов. Ил. 19, библиогр. 10.

Полный текст: PDF файл (2525 kB)

Реферативные базы данных:
УДК: 519.172.2
Статья поступила: 02.08.2001

Образец цитирования: О. В. Бородин, Х. Брусма, А. Н. Глебов, Я. ван ден Хойвел, “Минимальные степени и хроматические числа квадратов плоских графов”, Дискретн. анализ и исслед. опер., сер. 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://www.ams.org/mathscinet-getitem?mr=1918258}
\zmath{https://zbmath.org/?q=an:1012.05074}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da228
  • http://mi.mathnet.ru/rus/da/v8/s1/i4/p9

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. van den Heuvel J., McGuinness S., “Coloring the square of a planar graph”, J Graph Theory, 42:2 (2003), 110–124  crossref  mathscinet  zmath  isi  scopus
    2. О. В. Бородин, А. О. Иванова, Т. К. Неустроева, “$2$-дистанционная раскраска разреженных плоских графов”, Сиб. электрон. матем. изв., 1 (2004), 76–90  mathnet  mathscinet  zmath
    3. О. В. Бородин, А. Н. Глебов, А. О. Иванова, Т. К. Неустроева, В. А. Ташкинов, “Достаточные условия $2$-дистанционной $\Delta+1$ раскрашиваемости плоских графов”, Сиб. электрон. матем. изв., 1 (2004), 129–141  mathnet  mathscinet  zmath
    4. О. В. Бородин, А. О. Иванова, Т. К. Неустроева, “Предписанная $(p,q)$-раскраска разреженных плоских графов”, Сиб. электрон. матем. изв., 3 (2006), 355–361  mathnet  mathscinet  zmath
    5. Calamoneri T., “The L(h, k)-labelling problem: A survey and annotated bibliography”, The Computer Journal, 49:5 (2006), 585–608  crossref  isi  scopus
    6. Broersma H., Fomin F.V., Golovach P.A., Woeginger G.J., “Backbone colorings for graphs: Tree and path backbones”, J Graph Theory, 55:2 (2007), 137–152  crossref  mathscinet  zmath  isi  elib  scopus
    7. Broersma H., Marchal B., Paulusma D., Salman A.N.M., “Improved upper bounds for lambda-backbone colorings along matchings and stars”, SOFSEM 2007: Theory and Practice of Computer Science, Proceedings, Lecture Notes in Computer Science, 4362, 2007, 188–199  crossref  mathscinet  zmath  isi
    8. О. В. Бородин, А. О. Иванова, “Предписанная 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
    9. Borodin O.V., Ivanova A.O., “2-distance (Delta+2)-coloring of planar graphs with girth six and Delta >= 18”, Discrete Math, 309:23–24 (2009), 6496–6502  crossref  mathscinet  zmath  isi  elib  scopus
    10. Borodin O.V., Ivanova A.O., “List 2-distance (Delta+2)-coloring of planar graphs with girth six”, European J Combin, 30:5 (2009), 1257–1262  crossref  mathscinet  zmath  isi  elib  scopus
    11. Broersma H.J., Fujisawa J., Marchal L., Paulusma D., Salman A.N.M., Yoshimoto K., “lambda-backbone colorings along pairwise disjoint stars and matchings”, Discrete Math, 309:18 (2009), 5596–5609  crossref  mathscinet  zmath  isi  elib  scopus
    12. Amini O., Esperet L., van den Heuvel J., “A Unified Approach to Distance-Two Colouring of Planar Graphs”, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, 273–282  crossref  mathscinet  isi
    13. А. О. Иванова, “Предписанная 2-дистанционная $(\Delta+1)$-раскраска плоских графов с обхватом не менее 7”, Дискретн. анализ и исслед. опер., 17:5 (2010), 22–36  mathnet  mathscinet  zmath
    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. 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
    20. Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539  crossref  mathscinet  zmath  isi  elib  scopus
    21. 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
    22. 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
    23. 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
    24. 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
    25. 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
    26. 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
    27. О. В. Бородин, А. О. Иванова, “Легкие и низкие $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
    28. 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
    29. 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
    30. О. В. Бородин, А. О. Иванова, Д. В. Никифоров, “Низкие и легкие $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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:320
    Полный текст:95
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019