Главная Новости Оформление статьи Архив Авторы Поиск Вход
Номера
2019: 1
2018: 1 2 3 4 5 6
2017: 1 2 3 4 5 6
2016: 1 2 3 4 5 6
2015: 1 2 3 4 5 6
2014: 1 2 3 4 5 6
2013: 1 2 3 4 5 6
2012: 1 2 3 4 5 6
2011: 1 2 3 4 5 6
2010: 1 2 3 4 5 6
2009: 1 2 3 4 5 6
2008: 1 2 3 4 5 6
2007: 1 2 3 4 5 6
2006: 1 2 3 4 5 6
2005: 1 2 3 4 5 6
2004: 1 2 3 4 5 6
2003: 1 2 3 4 5 6
2002: 1 2 3 4 5 6
2001: 1 2 3 4 5 6
2000: 1 2 3 4 5 6
1999: 1 2 3 4 5 6
1998: 1 2 3 4 5 6
1997: 1 2 3 4 5 6
1996: 1 2 3 4 5 6
1995: 1 2 3 4 5 6
1994: 1 2 3 4 5 6
1993: 1 2 3 4 5 6

СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ

АННОТАЦИИ

Бородин О. В., Косточка А. В. Вершинные разбиения разреженных графов на независимое множество и подграф максимальной степени не более 1 // Том 52 (2011), Номер 5, стр. 1004–1010 
Граф $G$ называется $(1,0)$-{\it раскрашиваемым},
если множество его вершин можно разбить на подмножества  $V_1$ и $V_0$ так,
чтобы в подграфе $G[V_1]$ каждая вершина имела степень не больше $1$,
а $G[V_0]$ не содержал ребер.
Доказано, что всякий граф c максимальной средней степенью не более $\frac {12}{5}$
является $(1,0)$-раскрашиваемым.
В частности, отсюда следует $(1,0)$-раскрашиваемость
любого плоского графа обхвата не менее  $12$.
С другой стороны, построены графы с максимальной
средней степенью, сколь угодно близкой (сверху) к $\frac {12}{5}$,
которые не имеют $(1,0)$-раскраски.
© Сибирский Математический Журнал, 2003-2006