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

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

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



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






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


Сиб. электрон. матем. изв., 2006, том 3, страницы 441–450 (Mi semr219)  

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

Статьи

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

О. В. Бородинa, А. О. Ивановаb, Т. К. Неустроеваb

a Институт математики им. С. Л. Соболева СО РАН
b Якутский государственный университет им. М. К. Аммосова

Аннотация: A trivial lower bound for the $2$-distance chromatic number $\chi_2(G)$ of any graph $G$ with maximum degree $\Delta$ is $\Delta+1$. It is known that if $G$ is planar and its girth is at least $7$, then for large enough $\Delta$ this bound is sharp, while for girth $6$ it is not true. We prove that if $G$ is planar, its girth is $6$, every edge is incident with a $2$-vertex, and $\Delta\ge31$, then $\chi_2(G)=\Delta+1$.

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

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

Образец цитирования: О. В. Бородин, А. О. Иванова, Т. К. Неустроева, “Достаточные условия минимальной $2$-дистанционной раскрашиваемости плоских графов с обхватом $6$”, Сиб. электрон. матем. изв., 3 (2006), 441–450

Цитирование в формате AMSBIB
\RBibitem{BorIvaNeu06}
\by О.~В.~Бородин, А.~О.~Иванова, Т.~К.~Неустроева
\paper Достаточные условия минимальной $2$-дистанционной раскрашиваемости плоских графов с~обхватом~$6$
\jour Сиб. электрон. матем. изв.
\yr 2006
\vol 3
\pages 441--450
\mathnet{http://mi.mathnet.ru/semr219}
\zmath{https://zbmath.org/?q=an:1119.05039}


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

    ОТПРАВИТЬ: 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. 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
    2. О. В. Бородин, А. О. Иванова, “Предписанная 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
    3. 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
    4. 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
    5. А. О. Иванова, “Предписанная 2-дистанционная $(\Delta+1)$-раскраска плоских графов с обхватом не менее 7”, Дискретн. анализ и исслед. опер., 17:5 (2010), 22–36  mathnet  mathscinet  zmath
    6. Borodin O.V., Ivanova A.O., Montassier M., Ochem P., Raspaud A., “Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most $k$”, J. Graph Theory, 65:2 (2010), 83–93  crossref  mathscinet  zmath  isi  elib
    7. О. В. Бородин, А. О. Иванова, “Инъективная $(\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
    8. О. В. Бородин, А. О. Иванова, “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
    9. 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
    10. 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
    11. Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539  crossref  mathscinet  mathscinet  zmath  isi  elib
    12. 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
    13. 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
  • Просмотров:
    Эта страница:315
    Полный текст:49
    Литература:33
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020