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

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

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



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






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


Сиб. электрон. матем. изв., 2004, том 1, страницы 129–141 (Mi semr12)  

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

Статьи

Достаточные условия $2$-дистанционной $\Delta+1$ раскрашиваемости плоских графов

О. В. Бородин, А. Н. Глебов, А. О. Иванова, Т. К. Неустроева, В. А. Ташкинов


Аннотация: A trivial lower bound for the $2$-distance chromatic number $\chi_2(G)$ of any graph $G$ with maximum degree $\Delta$ is $\Delta+1$. We prove that if $G$ is planar and its girth is at least $7$, then $\chi_2(G)=\Delta+1$ whenever $\Delta\ge 30$. On the other hand, we construct planar graphs with girth $5$ and $6$ that have arbitrarily large $\Delta$ and $\chi_2(G)>\Delta+1$.

Полный текст: PDF файл (229 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:
Тип публикации: Статья
УДК: 519.172.2
MSC: 05С15
Поступила 1 декабря 2004 г., опубликована 14 декабря 2004 г.

Образец цитирования: О. В. Бородин, А. Н. Глебов, А. О. Иванова, Т. К. Неустроева, В. А. Ташкинов, “Достаточные условия $2$-дистанционной $\Delta+1$ раскрашиваемости плоских графов”, Сиб. электрон. матем. изв., 1 (2004), 129–141

Цитирование в формате AMSBIB
\RBibitem{BorGleIva04}
\by О.~В.~Бородин, А.~Н.~Глебов, А.~О.~Иванова, Т.~К.~Неустроева, В.~А.~Ташкинов
\paper Достаточные условия $2$-дистанционной $\Delta+1$ раскрашиваемости плоских графов
\jour Сиб. электрон. матем. изв.
\yr 2004
\vol 1
\pages 129--141
\mathnet{http://mi.mathnet.ru/semr12}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2132454}
\zmath{https://zbmath.org/?q=an:1076.05032}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/semr12
  • http://mi.mathnet.ru/rus/semr/v1/p129

    ОТПРАВИТЬ: 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. О. В. Бородин, А. О. Иванова, Т. К. Неустроева, “Достаточные условия 2-дистанционной $(\Delta+1)$-раскрашиваемости плоских графов с обхватом 6”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 12:3 (2005), 32–47  mathnet  mathscinet  zmath
    2. О. В. Бородин, А. О. Иванова, Т. К. Неустроева, “Предписанная $(p,q)$-раскраска разреженных плоских графов”, Сиб. электрон. матем. изв., 3 (2006), 355–361  mathnet  mathscinet  zmath
    3. О. В. Бородин, А. О. Иванова, Т. К. Неустроева, “Достаточные условия минимальной $2$-дистанционной раскрашиваемости плоских графов с обхватом $6$”, Сиб. электрон. матем. изв., 3 (2006), 441–450  mathnet  zmath
    4. О. В. Бородин, А. О. Иванова, Т. К. Неустроева, “Предписанная 2-дистанционная $(\Delta+1)$-раскраска плоских графов с заданным обхватом”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 14:3 (2007), 13–30  mathnet  mathscinet  zmath; J. Appl. Industr. Math., 2:3 (2008), 317–328  crossref
    5. Borodin O.V., Ivanova A.O., Kostochka A.V., Sheikh N.N., “Minimax degrees of quasiplanar graphs with no short cycles other than triangles”, Taiwanese J Math, 12:4 (2008), 873–886  mathscinet  zmath  isi  elib
    6. Dvorak Z., Kral D., Nejedly P., Skrekovski R., “Coloring squares of planar graphs with girth six”, European J Combin, 29:4 (2008), 838–849  crossref  mathscinet  zmath  isi
    7. Dvorak Z., Skrekovski R., Tancer M., “List-coloring squares of sparse subcubic graphs”, SIAM J Discrete Math, 22:1 (2008), 139–159  crossref  mathscinet  zmath  isi
    8. Cranston D.W., Kim S.-J., “List-coloring the square of a subcubic graph”, J Graph Theory, 57:1 (2008), 65–87  crossref  mathscinet  zmath  isi  elib
    9. О. В. Бородин, А. О. Иванова, “Предписанная 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
    10. Borodin O.V., Ivanova A.O., “$2$-distance $(\Delta+2)$-coloring of planar graphs with girth six and $\Delta\ge 18$”, Discrete Math., 309:23-24 (2009), 6496–6502  crossref  mathscinet  zmath  isi  elib
    11. Dvorak Z., Kral D., Nejedly P., Skrekovski R., “Distance constrained labelings of planar graphs with no short cycles”, Discrete Appl Math, 157:12 (2009), 2634–2645  crossref  mathscinet  zmath  isi
    12. 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
    13. А. О. Иванова, “Предписанная 2-дистанционная $(\Delta+1)$-раскраска плоских графов с обхватом не менее 7”, Дискретн. анализ и исслед. опер., 17:5 (2010), 22–36  mathnet  mathscinet  zmath
    14. Zhang X., Liu G., Wu J.-L., “k-forested coloring of planar graphs with large girth”, Proc Japan Acad Ser A Math Sci, 86:10 (2010), 169–173  crossref  mathscinet  zmath  isi  elib
    15. О. В. Бородин, А. О. Иванова, “Инъективная $(\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
    16. О. В. Бородин, А. О. Иванова, “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
    17. 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
    18. Calamoneri T., “The L(h, k)-Labelling Problem: An Updated Survey and Annotated Bibliography”, The Computer Journal, 54:8 (2011), 1344–1371  crossref  isi
    19. Borodin O.V., Ivanova A.O., “List 2-facial 5-colorability of plane graphs with girth at least 12”, Discrete Math, 312:2 (2012), 306–314  crossref  mathscinet  zmath  isi  elib
    20. Bu Yu., Zhu X., “An Optimal Square Coloring of Planar Graphs”, J. Comb. Optim., 24:4 (2012), 580–592  crossref  mathscinet  mathscinet  zmath  isi  elib
    21. Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539  crossref  mathscinet  mathscinet  zmath  isi  elib
    22. Bonamy M., Leveque B., Pinlou A., “Graphs with Maximum Degree Delta >= 17 and Maximum Average Degree Less Than 3 Are List 2-Distance (Delta+2)-Colorable”, Discrete Math., 317 (2014), 19–32  crossref  mathscinet  zmath  isi  elib
    23. Zhu H., Hou L., Chen W., Lu X., “The l(P, Q)-Labelling of Planar Graphs Without 4-Cycles”, Discrete Appl. Math., 162 (2014), 355–363  crossref  mathscinet  zmath  isi  elib
    24. Bonamy M., Leveque B., Pinlou A., “2-Distance Coloring of Sparse Graphs”, J. Graph Theory, 77:3 (2014), 190–218  crossref  mathscinet  zmath  isi  elib
    25. Bonamy M., Leveque B., Pinlou A., “List Coloring the Square of Sparse Graphs With Large Degree”, Eur. J. Comb., 41 (2014), 128–137  crossref  mathscinet  zmath  isi  elib
    26. Dong W., Xu B., “2-Distance Coloring of Planar Graphs With Girth 5”, J. Comb. Optim., 34:4 (2017), 1302–1322  crossref  mathscinet  zmath  isi  scopus
    27. 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
    28. Dong W., Lin W., “On 2-Distance Coloring of Plane Graphs With Girth 5”, Discret Appl. Math., 217:3 (2017), 495–505  crossref  mathscinet  zmath  isi  scopus
    29. Yi D., Zhu J., Feng L., Wang J., Yang M., “Optimal R-Dynamic Coloring of Sparse Graphs”, J. Comb. Optim., 38:2 (2019), 545–555  crossref  mathscinet  zmath  isi  scopus
    30. Kang R.J., van Loon W., “Tree-Like Distance Colouring For Planar Graphs of Sufficient Girth”, Electron. J. Comb., 26:1 (2019), P1.23  mathscinet  zmath  isi
    31. Dong W. Xu B., “2-Distance Coloring of Planar Graphs Without 4-Cycles and 5-Cycles”, SIAM Discret. Math., 33:3 (2019), 1297–1312  crossref  mathscinet  zmath  isi  scopus
    32. Bonamy M., Cranston D.W., Postle L., “Planar Graphs of Girth At Least Five Are Square (Delta+2)-Choosable”, J. Comb. Theory Ser. B, 134 (2019), 218–238  crossref  mathscinet  zmath  isi  scopus
  • Просмотров:
    Эта страница:267
    Полный текст:59
    Литература:27
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021