Co-author(s) :

Khachatrian Hrant

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:

Elsevier

Date of publication:

31.07.2017

Identifier:

oai:noad.sci.am:136140

DOI:

10.1016/j.dam.2017.04.005

ISSN:

0166-218X

Language:

English

Journal or Publication Title:

Discrete Applied Mathematics

Volume:

226

URL:

click here to follow the link

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

Country:

Armenia

Indexing:

WOS