Mathematics

Some bounds on the number of colors in interval edge-colorings of graphs

[Некоторые оценки числа цветов в интервальных реберных раскрасках графов]

P. A. Petrosyan, L. N. Muradyan

Yerevan State University, Faculty of Informatics and Applied Mathematics

Аннотация: Реберная раскраска графа $G$ в цвета $1,\ldots,t$ называется интервальной t-раскраской, если все цвета использованы и цвета ребер, инцидентных любой вершине графа $G$, различны и образуют интервал целых чисел. Вершина $v$ графа $G=(V,E)$ называется доминантной, если $d_{G}(v)=|V|-1$, где $d_{G}(v)$ – степень вершины $v$ в графе $G$. В настоящей работе показано, что если граф $G$ с доминантной вершиной $u$ обладает интервальной $t$-раскраской, то $t\leq |V|+2\Delta(G-u)-1$, где $\Delta(G)$ – максимальная степень вершин в графе $G$. В работе также показано, что если $k$-связный граф $G=(V,E)$ обладает интервальной $t$-раскраской, то $t\leq 1+\left(\left\lfloor \dfrac{|V|-2}{k}\right\rfloor+2\right)(\Delta(G)-1)$. Кроме того, если граф $G$ также является двудольным, то полученную верхнюю оценку можно улучшить до $t\leq 1+\left(\left\lfloor \dfrac{|V|-2}{k}\right\rfloor+1\right)(\Delta(G)-1)$. В конце работы обсуждается достижимость полученных верхних оценок числа цветов в интервальных раскрасках рассмотренных графов.

Ключевые слова: edge-coloring, interval edge-coloring, $k$-connected graph, bipartite graph, dominating vertex

MSC: Primary 05C15; Secondary 05C40

Поступила в редакцию: 30.08.2024
Исправленный вариант: 07.10.2024
Принята в печать: 24.10.2024

Язык публикации: английский

DOI: 10.46991/PYSU:A.2024.58.2.057