|
|
Сиб. электрон. матем. изв., 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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
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
   -
О. В. Бородин, А. О. Иванова, “Предписанная 2–дистанционная $(\Delta+2)$-раскраска плоских графов с обхватом 6 и $\Delta\ge24$”, Сиб. матем. журн., 50:6 (2009), 1216–1224
 ; 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  -
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
-
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
-
А. О. Иванова, “Предписанная 2-дистанционная $(\Delta+1)$-раскраска плоских графов с обхватом не менее 7”, Дискретн. анализ и исслед. опер., 17:5 (2010), 22–36
-
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
-
О. В. Бородин, А. О. Иванова, “Инъективная $(\Delta+1)$-раскраска плоских графов с обхватом 6”, Сиб. матем. журн., 52:1 (2011), 30–38 ; O. V. Borodin, A. O. Ivanova, “Injective $(\Delta+1)$-coloring of planar graphs with girth 6”, Siberian Math. J., 52:1 (2011), 23–29
-
О. В. Бородин, А. О. Иванова, “2-дистанционная 4-раскраска плоских субкубических графов”, Дискретн. анализ и исслед. опер., 18:2 (2011), 18–28 ; O. V. Borodin, A. O. Ivanova, “2-distance 4-coloring of planar subcubic graphs”, J. Appl. Industr. Math., 5:4 (2011), 535–541
-
Borodin O.V., Ivanova A.O., “List injective colorings of planar graphs”, Discrete Math., 311:2–3 (2011), 154–165
-
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
-
Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539
-
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
-
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
|
| Просмотров: |
| Эта страница: | 315 | | Полный текст: | 49 | | Литература: | 33 |
|
Пользовательское соглашение