- Слабое вырождение плоских графов без 4- и 6-циклов (arXiv)
Автор : Тао Ван
Аннотация: Граф называется k-вырожденным, если каждый подграф H имеет вершину v с dH(v)≤k. Класс вырожденных графов играет важную роль в теории раскраски графов. Замечено, что каждый k-вырожденный граф (k+1)-выбираем и (k+1)-DP-раскрашиваем. Бернштейн и Ли определили обобщение k-вырожденных графов, которое называется \emph{слабо k-вырожденным}. Слабое вырождение плюс один является верхней границей для многих параметров раскраски графа, таких как число выбора, число DP-хроматики и число DP-краски. В этой статье мы даем два достаточных условия слабой 2-вырожденности плоского графа без 4- и 6-циклов, что означает, что каждый такой граф является 3-DP-раскрашиваемым и почти двудольным, где граф почти- двудольным, если его множество вершин можно разбить на независимое множество и ациклическое множество
2. Об интервальных раскрасках планарных графов (arXiv)
Автор : Арсен Амбарцумян, Левон Мурадян
Аннотация: n-раскраска ребер графа G цветами 1,…,t называется \emph{интервальной t-раскраской}, если используются все цвета и цвета ребер, инцидентных каждой вершине графа G, различны и образуют интервал целых чисел. В 1990 году Камалян доказал, что если граф G хотя бы с одним ребром имеет интервальную t-раскраску, то t≤2|V(G)|−3. В 2002 году Аксенович улучшил эту верхнюю границу для плоских графов: если планарный граф G допускает интервальную t-раскраску, то t≤116|V(G)|. В той же статье Аксенович выдвинул гипотезу о том, что если планарный граф G имеет интервальную t-раскраску, то t≤32|V(G)|. В этой статье мы подтверждаем гипотезу, показывая, что если планарный граф G допускает интервальную t-раскраску, то t≤3|V(G)|−42. Мы также доказываем, что если внешнепланарный граф G имеет интервальную t-раскраску, то t≤|V(G)|−1. Более того, все эти верхние оценки точны
