From edge-coloring to strong edge-coloring

In this paper we study a generalization of both proper edge-coloring and strong edge-coloring: k-intersection edge-coloring, introduced by Muthu, Narayanan and Subramanian. In this coloring, the set S(v) of colors used by edges incident to a vertex v does not intersect S(u) on more than k colors when u and v are adjacent. We provide some sharp upper and lower bounds for χ′k-int for several classes of graphs. For l-degenerate graphs we prove that χ′k-int(G)≤(l+1)Δ−l(k−1)−1. We improve this bound for subcubic graphs by showing that χ′2-int(G)≤6. We show that calculating χ′k-int(Kn) for arbitrary values of k and n is related to some problems in combinatorial set theory and we provide bounds that are tight for infinitely many values of n. Furthermore, for complete bipartite graphs we prove that χ′k-int(Kn, m)=⌈mn/k⌉. Finally, we show that computing χ′k-int(G) is NP-complete for every k≥1.