From edge-coloring to strong edge-coloring

Valentin Borozan¹ ; Gerard Jennhwa Chang² ; Nathann Cohen³ ; Shinya Fujita⁴ ; Narayanan Narayanan⁵ ; Reza Naserasr³ ; Petru Valicov⁶

¹Alfréd Rényi Institute of Mathematics, Budapest, Hungary
²Department of Mathematics, National Taiwan University, Taipei, 10617, Taiwan
³CNRS, LRI, University Paris-Sud 11, Orsay, France
⁴Department of Integrated Design Engineering, Maebashi Institute of Technology, 460-1, Kamisadori, Maebashi, Japan
⁵Indian Institute of Technology, Chennai
⁶LIF - Université Aix-Marseille

The electronic journal of combinatorics, Tome 22 (2015) no. 2

Résumé

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.

Détail

DOI : 10.37236/3529

Classification : 05C15, 05C35, 05C07
Mots-clés : edge colorings, extremal combinatorics, maximum degree bounds, complete bipartite graphs, NP-completeness