Mathematics

On deficiency of complete 3-partite and 4-partite graphs

[Дефицит некоторых полных трехдольных и четырехдольных графов]

V. D. Tsirunyan

Yerevan State University, Faculty of Mathematics and Mechanics

Аннотация: Отображение $\alpha:E(G)\rightarrow {1,\ldots,t}$ называется правильной $t$-раскраской ребер графа $G,$ если используются все цвета и для любых двух смежных ребер $e, e^{\prime} \in E(G)$ выполняется $\alpha(e)\neq \alpha(e^{\prime}).$ Если $\alpha$ – правильная раскраска ребер графа $G$ и $v \in V(G),$ то спектром вершины $v,$ обозначаемым через $S(v, \alpha),$ называется множество всех цветов ребер, инцидентных вершине $v.$ Дефицитом раскраски $\alpha$ в вершине $v \in V(G),$ обозначаемым $\mathrm{def}(v, \alpha),$ называется минимальное количество целых чисел, которые необходимо добавить к множеству $S(v, \alpha),$ чтобы оно образовывало интервал. Дефицит правильной раскраски $\alpha$ графа $G$, обозначаемый $\mathrm{def}(G, \alpha),$ определяется как сумма $\displaystyle\sum_{v \in V(G)} \mathrm{def}(v, \alpha).$ Дефицит графа $G,$ обозначаемый $\mathrm{def}(G),$ определяется следующим образом: $\mathrm{def}(G) = \min_\alpha \mathrm{def}(G, \alpha),$ где минимум берется по всем возможным правильным раскраскам ребер графа $G.$ В 2019 г. Давтян, Минасян и Петросян получили верхнюю оценку дефицита полных многодольных графов. В настоящей работе эта оценка улучшена для полных трехдольных графов, а также некоторых полных четырехдольных графов. Кроме того, для всех трехдольных графов, содержащих не более 10 вершин, доказано, что их дефицит не превышает количества вершин графа.

Ключевые слова: proper edge-coloring, interval (consecutive) coloring, deficiency, complete multipartite graph, computer experiments

MSC: 05C15

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

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

DOI: 10.46991/PYSU:A.2025.59.3.084