Mathematics

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

V. D. Tsirunyan

Yerevan State University, Faculty of Mathematics and Mechanics

Abstract: A proper $t$-edge-coloring of a graph $G$ is a mapping $\alpha: E(G)\rightarrow \{1,\ldots,t\}$ such that all colors are used, and $\alpha(e)\neq \alpha(e^{\prime})$ for every pair of adjacent edges $e,e^{\prime}\in E(G)$. If $\alpha$ is a proper edge-coloring of a graph $G$ and $v\in V(G)$, then the spectrum of a vertex $v$, denoted by $S\left(v,\alpha \right)$, is the set of all colors appearing on edges incident to $v$. The deficiency of $\alpha$ at vertex $v\in V(G)$, denoted by $\mathrm{def}(v,\alpha)$, is the minimum number of integers that must be added to $S\left(v,\alpha \right)$ to form an interval, and \emph{the deficiency $\mathrm{def}\left(G,\alpha\right)$ of a proper edge-coloring $\alpha$ of $G$} is defined as the sum $\displaystyle\sum_{v\in V(G)}\mathrm{def}(v,\alpha)$. The deficiency of a graph $G$, denoted by $\mathrm{def}(G)$, is defined as follows: $\mathrm{def}(G)=\min_{\alpha}\mathrm{def}\left(G,\alpha\right)$, where the minimum is taken over all possible proper edge-colorings of $G$. In 2019, Davtyan, Minasyan, and Petrosyan provided an upper bound on the deficiency of complete multipartite graphs. In this paper, we improve this bound for complete tripartite and some complete 4-partite graphs. We also confirm the conjecture that states the deficiency of a graph is bounded by the number of vertices of the graph for all tripartite graphs containing up to 10 vertices.

Keywords: proper edge-coloring, interval (consecutive) coloring, deficiency, complete multipartite graph, computer experiments

MSC: 05C15

Received: 20.11.2025
Revised: 07.12.2025
Accepted: 20.12.2025

Language: English

DOI: 10.46991/PYSU:A.2025.59.3.084