From Edge-Coloring to Strong Edge-Coloring
From Edge-Coloring to Strong Edge-Coloring
复制标题
DOI：
10.37236/3529
复制
发表时间：
2015-04
期刊：
影响因子：
--
通讯作者：
V. Borozan;Gerard Jennhwa;Chang;Nathann Cohen;S. Fujita;N. Narayanan;R. Naserasr;Petru Valicov
中科院分区：
文献类型：
--
作者：
V. Borozan;Gerard Jennhwa;Chang;Nathann Cohen;S. Fujita;N. Narayanan;R. Naserasr;Petru Valicov
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 $\chi'_{k\text{-int}}$ for several classes of graphs. For $l$-degenerate graphs we prove that $\chi'_{k\text{-int}}(G)\leq (l+1)\Delta -l(k-1)-1$. We improve this bound for subcubic graphs by showing that $\chi'_{2\text{-int}}(G)\leq 6$. We show that calculating $\chi'_{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'_{k\text{-int}}(K_{n,m}) = \left\lceil \frac{mn}{k}\right\rceil$. Finally, we show that computing $\chi'_{k\text{-int}}(G)$ is NP-complete for every $k\geq 1$. An addendum was added to this paper on Jul 4, 2015.
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 $\chi'_{k\text{-int}}$ for several classes of graphs. For $l$-degenerate graphs we prove that $\chi'_{k\text{-int}}(G)\leq (l+1)\Delta -l(k-1)-1$. We improve this bound for subcubic graphs by showing that $\chi'_{2\text{-int}}(G)\leq 6$. We show that calculating $\chi'_{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'_{k\text{-int}}(K_{n,m}) = \left\lceil \frac{mn}{k}\right\rceil$. Finally, we show that computing $\chi'_{k\text{-int}}(G)$ is NP-complete for every $k\geq 1$. An addendum was added to this paper on Jul 4, 2015.