Бородин О. В., Косточка А. В.
Вершинные разбиения разреженных графов на независимое множество и подграф максимальной степени не более 1

Граф G называется (1, 0)-раскрашиваемым, если множество его вершин можно разбить на подмножества V₁ и V₀ так, чтобы в подграфе G[V₁] каждая вершина имела степень не больше 1, а G[V₀] не содержал ребер. Доказано, что всякий граф c максимальной средней степенью не более является (1, 0)- раскрашиваемым. В частности, отсюда следует (1, 0)-раскрашиваемость любого плоского графа обхвата не менее 12. С другой стороны, построены графы с максимальной средней степенью, сколь угодно близкой (сверху) к , которые не имеют (1, 0)-раскраски.
Фактически в работе получен более сильный результат: найдено неулучшаемое достаточное условие (1, 0)-раскрашиваемости графа G в терминах минимума, Ms(G), разности 6|V (A)|−5|E (A)| по всем подграфам A графа G. А именно, доказано, что всякий граф G с Ms(G) ≥ −2 является (1, 0)-раскрашиваемым, и построена бесконечная серия (1, 0)-нераскрашиваемых графов G с Ms(G) = −3.

Borodin O. V., Kostochka A. V.
Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1

A graph G is (1, 0)-colorable if its vertex set can be partitioned into subsets V₁ and V₀ so that in G[V₁] every vertex has degree at most 1, while G[V₀] is edgeless. We prove that every graph with maximum average degree at most is (1, 0)-colorable. In particular, every planar graph with girth at least 12 is (1, 0)-colorable. On the other hand, we construct graphs with the maximum average degree arbitrarily close (from above) to which are not (1, 0)-colorable.

In fact, we prove a stronger result by establishing the best possible sufficient condition for the (1, 0)-colorability of a graph G in terms of the minimum, Ms(G), of 6|V (A)|−5|E (A)| over all subgraphs A of G. Namely, every graph G with Ms(G) ≥ −2 is proved to be (1, 0)-colorable, and we construct an infinite series of non-(1, 0)-colorable graphs G with Ms(G) = −3.

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

• PDF file
• PostScript file