|
Сибирский математический журнал, 2011, том 52, номер 1, страницы 30–38
(Mi smj2175)
|
|
|
|
Эта публикация цитируется в 17 научных статьях (всего в 17 статьях)
Инъективная $(\Delta+1)$-раскраска плоских графов с обхватом 6
О. В. Бородинa, А. О. Ивановаb a Институт математики им. С. Л. Соболева СО РАН, Новосибирск
b Институт математики при Якутском гос. университете, Якутск
Аннотация:
Раскраска графа называется инъективной, если любые две вершины, между которыми существует цепь длины 2, получают разные цвета. Ясно, что минимальное число цветов $\chi_i(G)$ в инъективной раскраске любого графа $G$ не меньше, чем его максимальная степень $\Delta(G)$. Существуют плоские графы с обхватом $g\ge6$ и $\chi_i=\Delta+1$ для любой $\Delta\ge2$. Доказано, что каждый плоский граф с $\Delta\ge18$ и $g\ge6$ имеет $\chi_i\le\Delta+1$.
Ключевые слова:
плоский граф, инъективная раскраска, обхват.
Статья поступила: 03.02.2010
Образец цитирования:
О. В. Бородин, А. О. Иванова, “Инъективная $(\Delta+1)$-раскраска плоских графов с обхватом 6”, Сиб. матем. журн., 52:1 (2011), 30–38; Siberian Math. J., 52:1 (2011), 23–29
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/smj2175 https://www.mathnet.ru/rus/smj/v52/i1/p30
|
Статистика просмотров: |
Страница аннотации: | 405 | PDF полного текста: | 98 | Список литературы: | 56 | Первая страница: | 1 |
|