Бородин О. В., Иванова А. О.
Инъективная (Δ + 1)-раскраска плоских графов с обхватом 6

Раскраска графа называется инъективной, если любые две вершины, между которыми существует цепь длины 2, получают разные цвета. Ясно, что минимальное число цветов χ _i (G) в инъективной раскраске любого графа G не меньше, чем его максимальная степень Δ(G). Существуют плоские графы с обхватом g ≥ 6 и χ _i = Δ + 1 для любой Δ ≥ 2. Доказано, что каждый плоский граф с Δ ≥ 18 и g ≥ 6 имеет χ _i ≤ Δ + 1.

Borodin O. V. , Ivanova A. O.
Injective (Δ + 1)-coloring of planar graphs with girth 6

A vertex coloring of a graph G is called injective if every two vertices joined by a path of length 2 get different colors. The minimum number χ _i (G) of the colors required for an injective coloring of a graph G is clearly not less than the maximum degree Δ(G) of G. There exist planar graphs with girth g ≥ 6 and χ _i = Δ + 1 for any Δ ≥ 2. We prove that every planar graph with Δ ≥ 18 and g ≥ 6 has χ _i ≤ Δ + 1.

Полный текст статьи / Full texts:

• PDF file
• PostScript file