RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирский математический журнал // Архив

Сиб. матем. журн., 2011, том 52, номер 1, страницы 30–38 (Mi smj2175)

Эта публикация цитируется в 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$.

Ключевые слова: плоский граф, инъективная раскраска, обхват.

УДК: 519.17

Статья поступила: 03.02.2010


 Англоязычная версия: Siberian Mathematical Journal, 2011, 52:1, 23–29

Реферативные базы данных:


© МИАН, 2024