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 [18]. 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 x'(k-int) for several classes of graphs. For l-degenerate graphs we prove that x'(k-int)(G) <= (l + 1)Delta - l(k - 1) - 1. We improve this bound for subcubic graphs by showing that X'(2-int)(G) <= 6. We show that calculating X'(k-int) (K-n) 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 X'(k-int) (K-n,K-m) = [mn/k]. Finally, we show that computing X'(k-int) (G) is NP-complete for every k >= 1.