#### Title:

Further results on the deficiency of graphs

#### Author:

#### Type:

#### Co-author(s) :

#### Uncontrolled Keywords:

Proper edge-coloring ; Interval (consecutive) coloring ; Deficiency ; complete graph ; Near-complete graph

#### Abstract:

A proper t-edge-coloring of a graph G is a mapping α:E(G)→{1,…,t} such that all colors are used, and α(e)≠α(e′) for every pair of adjacent edges e,e′∈E(G). If α is a proper edge-coloring of a graph G and v∈V(G), then the spectrum of a vertex v, denoted by S(v,α), is the set of all colors appearing on edges incident to v. The deficiency of α at vertex v∈V(G), denoted by def(v,α), is the minimum number of integers which must be added to S(v,α) to form an interval, and the deficiency def(G,α) of a proper edge-coloring α of G is defined as the sum ∑v∈V(G)def(v,α). The deficiency of a graph G, denoted by def(G), is defined as follows: def(G)=minαdef(G,α), where minimum is taken over all possible proper edge-colorings of G. For a graph G, the smallest and the largest values of t for which it has a proper t-edge-coloring α with deficiency def(G,α)=def(G) are denoted by wdef(G) and Wdef(G), respectively. In this paper, we obtain some bounds on wdef(G) and Wdef(G). In particular, we show that for any l∈N, there exists a graph G such that def(G)>0 and Wdef(G)−wdef(G)≥l. It is known that for the complete graph K2n+1, def(K2n+1)=n (n∈N). Recently, Borowiecka-Olszewska, Drgas-Burchardt and Hałuszczak posed the following conjecture on the deficiency of near-complete graphs: if n∈N, then def(K2n+1−e)=n−1. In this paper, we confirm this conjecture.

#### Publisher:

#### Date of publication:

#### DOI:

#### ISSN:

#### Language:

#### Journal or Publication Title:

#### Volume:

#### URL:

#### Additional Information:

pet_petros@ipia.sci.am ; hrant.khachatrian@ysu.am

#### Affiliation:

Yerevan State University ; Department of informatics and applied mathematics ; Institute for Informatics and Automation Problems