2016/08/02 by Petros A. Petrosyan, Petrosyan, Petros A., Hrant Khachatrian +2
Computer Science · Mathematics · Neuroscience · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Nuclear Receptors and Signaling #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1608.00904
16 pages, 2 figures
openalex publication_date 2016/08/02 · arxiv created 2017/01/29 · arxiv updated 2017/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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∈ ℕ, 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∈ ℕ). Recently, Borowiecka-Olszewska, Drgas-Burchardt and Hałuszczak posed the following conjecture on the deficiency of near-complete graphs: if n∈ ℕ, then def(K2n+1-e)=n-1. In this paper, we confirm this conjecture.