Local gap colorings from edge labelings.
Axel Brandt, Brent Moran, Kapil Nepal, Florian Pfender, Devon Sigler · Australas. J Comb. · 2016
We study a local version of gap vertex–distinguishing edge coloring. From an edge labeling f : E → {1, . . . , k} of a graph G, an induced vertex coloring c is obtained by coloring the vertices with the greatest difference between incident edge labels. The local gap chromatic number χ∆(G) is the minimum k for which there exists an edge coloring such that c(u) 6= c(v) for all edges uv. We prove that χ(G) ≤ χ∆(G) ≤ χ(G)+1 for all graphs G, where χ(G) denotes the chromatic number of G. Further we find graph classes attaining both bounds.