From edge-coloring to strong edge-coloring (Q2341055)

Summary: In this paper we study a generalization of both proper edge-coloring and strong edge-coloring: \(k\)-intersection edge-coloring, introduced by \textit{R. Muthu} et al. [Discuss. Math., Graph Theory 29, No. 2, 411--418 (2009; Zbl 1194.05042)]. 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 \(\chi^\prime_{k\text{-int}}\) for several classes of graphs. For \(l\)-degenerate graphs we prove that \(\chi^\prime_{k\text{-int}}(G)\leq (l+1)\Delta -l(k-1)-1\). We improve this bound for subcubic graphs by showing that \(\chi^\prime_{2\text{-int}}(G)\leq 6\). We show that calculating \(\chi^\prime_{k\text{-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 \(\chi^\prime_{k\text{-int}}(K_{n,m}) = \left\lceil \frac{mn}{k}\right\rceil\). Finally, we show that computing \(\chi^\prime_{k\text{-int}}(G)\) is NP-complete for every \(k\geq 1\).