Аннотация:
Паросочетание $M$ графа $G$ называется почти сильным, если каждое ребро из $M$ инцидентно вершине степени один в графе, порожденном вершинами $M$. Правильная реберная раскраска графа $G$ называется почти сильной, если ребра, окрашенные в один и тот же цвет, составляют почти сильное паросочетание. Минимальное количество цветов, необходимое для почти сильной реберной раскраски, называется почти сильным хроматическим индексом графа $G$ и обозначается через $\chi'_{ss}(G)$. В этой работе предложен новый подход для построения почти сильных реберных раскрасок графов, а также получена верхняя оценка для почти сильного хроматического индекса внешнепланарных графов.
Полный текст:
PDF файл (2468 kB)