ON DEFICIENCY OF COMPLETE 3-PARTITE AND 4-PARTITE GRAPHS

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 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.