Header menu link for other important links
X
From Edge-Coloring to Strong Edge-Coloring
, Borozan Valentin, Jennhwa Chang Gerard, Cohen Nathann, Fujita Shinya, Naserasr Reza, Valicov Petru
Published in The Electronic Journal of Combinatorics
2015
Volume: 22
   
Issue: 2
Abstract

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

About the journal
PublisherThe Electronic Journal of Combinatorics
Open AccessNo