Главная Новости Оформление статьи Архив Авторы Поиск Вход
Номера
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

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

АННОТАЦИИ

Бородин О. В., Иванова А. О. Инъективная $(\Delta +1)$-раскраска плоских графов с обхватом $6$ // Том 52 (2011), Номер 1, стр. 30–38 
Раскраска графа называется {\it инъективной},
если любые две вершины, между которыми существует цепь длины 2, получают разные цвета.
Ясно, что минимальное число цветов $\chi_i(G)$ в инъективной раскраске любого графа $G$
не меньше, чем его максимальная степень $\Delta(G)$.
Существуют плоские графы с обхватом $g\ge 6$ и $\chi_i=\Delta+1$ для любой $\Delta\ge2$.
Доказано, что каждый плоский граф с $\Delta \ge 18$ и $g\ge6$ имеет
$\chi_i\le \Delta+1$.
© Сибирский Математический Журнал, 2003-2006