\documentclass[12pt]{article} \usepackage{e-jc} \usepackage[utf8]{inputenc} % EJC BLOCK \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \usepackage{amsthm,amsmath,amssymb} \usepackage{graphicx, latexsym, amsfonts, lscape, amscd, color, tikz} % THEOREMS ------------------------------------------------------- \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \usepackage{booktabs} % MATH ----------------------------------------------------------- \newcommand{\norm}[1]{\left\Vert#1\right\Vert} \newcommand{\abs}[1]{\left\vert#1\right\vert} \newcommand{\set}[1]{\left\{#1\right\}} \newcommand{\Real}{\mathbb R} \newcommand{\eps}{\varepsilon} \newcommand{\To}{\longrightarrow} \newcommand{\BX}{\mathbf{B}(X)} \newcommand{\A}{\mathcal{A}} % ---------------------------------------------------------------- \newcommand{\pictureee}[1]{#1} \def\kci{{\chik{k}}} \newcommand{\chik}[1]{\chi_{#1\text{-int}}'} \colorlet{myred}{red!50!black} \colorlet{myblue}{blue!50!black} \colorlet{mylightblue}{blue!30!green} \colorlet{mygreen}{green!80!black} \colorlet{mygreen2}{green!60!black} \begin{document} \title{\bf From edge-coloring to strong edge-coloring} \newcommand*\samethanks[1][\value{footnote}]{\footnotemark[#1]} \author{ Valentin Borozan\thanks{Alfréd Rényi Institute of Mathematics, Budapest, Hungary} \and Gerard Jennhwa Chang\thanks{Department of Mathematics, National Taiwan University, Taipei, 10617, Taiwan} \thanks{Taida Institute for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan} \thanks{National Center for Theoretical Sciences, Taipei Office, Taiwan} \footnote{E-mail: gjchang@math.ntu.edu.tw. Supported in part by the National Science Council under grant NSC101-2115-M-002-005-MY3.} \and Nathann Cohen\thanks{CNRS, LRI, University Paris-Sud 11, F-91405 Orsay Cedex, France} \and Shinya Fujita\thanks{International College of Arts and Sciences, Yokohama City University, 22-2 Seto, Kanazawa-ku, Yokohama 236-0027, Japan} \and Narayanan Narayanan\thanks{Indian Institute of Technology, Chennai}~~ \samethanks[2]~ \samethanks[6] \and Reza Naserasr\samethanks[6] \and Petru Valicov\samethanks[6]\thanks{Aix-Marseille Université, CNRS, LIF UMR 7279, 13288, Marseille, France} } \date{\dateline{July 2, 2013}{March 19, 2015}\\ \small Mathematics Subject Classifications: 05C15} \maketitle \begin{abstract} 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~\cite{MNS09}. 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 $\chik k$ for several classes of graphs. For $l$-degenerate graphs we prove that $\chik k(G)\leq (l+1)\Delta -l(k-1)-1$. We improve this bound for subcubic graphs by showing that $\chik 2(G)\leq 6$. We show that calculating $\chik k(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 $\kci(K_{n,m}) = \left\lceil \frac{mn}{k}\right\rceil$. Finally, we show that computing $\chik k(G)$ is NP-complete for every $k\geq 1$. \end{abstract} \section{Introduction} A \emph{proper edge-coloring} of a graph is an assignment of colors to the edges of $G$ such that every pair of adjacent edges receive different colors. Normally the aim is to use the smallest number of colors, which is denoted by $\chi'(G)$. This notion is one of the main theme of the theory of graph coloring and is studied extensively. Vizing's theorem, which claims that for every simple graph $G$ either $\chi'(G)=\Delta(G)$ or $\chi'(G)=\Delta(G)+1$ holds is among the most famous theorems in graph theory. In this work all edge-colorings are proper, so we will simply use the term edge-coloring. Furthermore all graphs are simple and finite. Various relaxations or generalizations of the concept of edge-coloring are studied. Among which is the notion of \emph{strong edge-coloring}, introduced by Fouquet and Jolivet~\cite{FJ83}, which not only requires for adjacent edges to have distinct colors, but also requires all edges adjacent to a given edge to receive different colors. Let $G$ be a graph and let $\phi: E(G) \to \mathbb N$ be an edge-coloring of $G$. For a vertex $v$ let $\phi(v)$ be the set of colors that appear on edges incident to $v$ (thus $|\phi(v)|=d(v)$). An equivalent definition of strong edge-coloring is to say that an edge-coloring $\phi$ is a strong edge-coloring if $|\phi(v)\cap \phi(u)|\leq 1$ for each pair $u,v$ of adjacent vertices (the color of $uv$ being the only color in common). This formulation led Muthu, Subramanian and the fifth author~\cite{MNS09} to introduce the following relaxed version: a \emph{$k$-intersection edge-coloring} of a graph $G$ is a (proper) edge-coloring in which we have $|\phi(v)\cap \phi(u)|\leq k$ for each pair $u,v$ of adjacent vertices. The \emph{$k$-intersection} \emph{chromatic} \emph{index} of $G$, denoted $\chik k(G)$, is the smallest number of colors in a possible $k$-intersection edge-coloring of $G$. Observe that not only $\chik 1(G)$ is the strong chromatic index of $G$, but also for $k\geq \Delta(G)$, $\chik k(G)=\chi'(G)$. Hence we assume $k\leq \Delta$. Vizing's theorem says that the chromatic number of a line graph is at most 1 more than its clique number. Recall that the square of a graph $G$, denoted $G^2$, is a graph on a same set of vertices where two vertices are adjacent if and only if they are at distance at most 2 in $G$. Then $\chik 1(G)$ is the chromatic number of the square of the line graph of $G$. Unlike line graphs, the difference between clique number and the chromatic number of a square of a line graph can be arbitrarily large. However Erd\H{o}s and Ne\v{s}et\v{r}il conjectured \cite{e88,en89} that for a given value of $\Delta$, the largest strong chromatic index is reached by graphs whose square of the line graph is a complete graph. Chung {\it et al.} \cite{2k2free} determined the largest clique of the square of the line graph of a graph of degree $\Delta$. Thus bounding the strong chromatic index of graphs of bounded maximum degree is studied by various authors, we refer to chapter 3 of \cite{thesepetru} for a survey. The aim of this work is to extend this study to the concept of $k$-intersection edge-coloring. We note that, capturing the flavors of both combinatorial set theory and coloring problems, determining $\chik k(G)$ proves to be an interesting challenge even for the simplest of graphs like complete graphs. Indeed we show how one can first of all use Corr\'adi's lemma~\cite{C69} to obtain a good lower bound on $\chik k(K_n)$. Then trying to obtain tighter bounds, we in fact obtain a strengthening of Corr\'adi's lemma. The structure of the paper is as follows. In the next section, after giving few examples, we give general bounds for $k$-intersection edge-chromatic number in terms of parameters like maximum degree or degeneracy. In Section~\ref{sec:complete} we give nearly tight bounds for $k$-intersection chromatic index of complete graphs and in Section~\ref{sec:complete_bipartite} we give an exact formula for the case of complete bipartite graphs. In the last section we prove that computing the $k$-intersection chromatic index is an NP-complete problem. We will use standard notations of graph theory. A subcubic graph is a graph of maximum degree 3. An $l$-degenerate graph is a graph any subgraph of which (including itself) has a vertex of degree at most $l$. \section{Examples and degree bounds} Since our colorings are always proper, $\chik k(G)\geq \Delta$ for any value of $k$. If we write $\Delta_e=\max \{ d(u)+d(v) | uv\in E(G)\}$, the next natural lower bound on $\chik k(G)$ is $\Delta_e-k$. Thus, in general we have \[ \chik k(G) \geq \max\{ \Delta_e-k, \Delta\}.\] \label{FirstInq} Our first result is that the equality holds for forests. \begin{proposition}\label{Trees} If $G$ is a forest, then $\chik k(G)= \max\{ \Delta_e-k, \Delta\}$. \end{proposition} \begin{proof} We use induction on the number $m$ of edges. Let $M := \max\{ \Delta_e-k, \Delta\}$. If $G$ is a disjoint union of stars (in particular when $m = 0$), then $M = \Delta$ and the claim is clear because every proper edge-coloring of a star is a $k$-intersection edge-coloring. Otherwise, consider an edge $vw$ between two non-leaf vertices of $G$ such that all neighbours of $v$ are leaves except $u$. Now, remove leaf neighbours of $v$ and edge-color what remains by the induction hypothesis. Up to a relabelling, we may assume that colors $1, 2, \ldots, d(w)$ are used for edges incident to $w$. We complete the coloring by using colors $M, M-1, \ldots, M-d(v)+ 2$ for the edges pending at $v$. The coloring that we obtain is a $k$-intersection $M$-edge-coloring, because $\max\{1, d(w) + d(v)-M\}$ colors are in the intersection for the edge $vw$ and $\max\{1, d(w) + d(v) -M\} \le k$. \end{proof} The previous proposition asserts that we know how to color forests, i.e. all 1-degenerate graphs. Some upper bounds for the strong chromatic index of $l$-degenerate graphs are given in \cite{CN12}, and we now provide a similar bound for $k$-intersection chromatic index. Our proof is based on the following observation on $l$-degenerate graph, first mentioned in \cite{CN12}, of the existence of a certain type of edges. \begin{observation}[\cite{CN12}] Let $G$ be a nonempty $l$-degenerate graph. There exists in $G$ an edge $uv$ such that $d(u)\leq l$ and $v$ has $\leq l$ neighbours of degree $> l$. \end{observation} %\input{lightedge.tex} \begin{center} \def\N{node[scale=.5,fill,circle]} \begin{tikzpicture} \draw (-3,0) -- (3,0); \draw \N (u) at (-3,0) {}; \draw \N (v) at (3,0) {}; \foreach \i in {-4,...,4}{ \draw (v) -- +(\i*.25,-1.5) \N {}; } \foreach \i in {-2,...,2}{ \draw (u) -- +(\i*.4,-1.5) \N {}; } \foreach \i in {-2,...,2}{ \draw (v) -- +(\i*.4,+1.5) \N {}; } \draw (u) +(-1,-1.3) rectangle +(1,-1.7); \draw (v) +(-1.2,-1.3) rectangle +(1.2,-1.7); \draw (v) +(-1.2,1.3) rectangle +(1.2,1.7); \draw node[text width=3cm, align=left, left] at (-4.2,-1.45) {\small $\leq l-1$ vertices of arbitrary degree}; \draw node[text width=2.5cm, align=right] at ( 5.8,-1.45) {\small vertices of degree at most $l$}; \draw node[text width=2.5cm, align=left] at ( 5.8,1.45) {\small $\leq l$ vertices of arbitrary degree}; \draw node[left=.2cm] at (-3,0) {$u$}; \draw node[right=.2cm] at (3,0) {$v$}; \end{tikzpicture} \end{center} \begin{proof} Assuming without loss of generality that $G$ is connected, let us consider the set $S\subseteq V(G)$ of all vertices of degree $\leq l$ in $G$: either there exists an edge between two vertices of $S$ (which is sufficient for our claim) or there exists by virtue of $l$-degeneracy a vertex $v$ of degree $\leq l$ in $G\backslash S$ which is adjacent to a vertex $u$ of $S$. \end{proof} We show how such an edge can help to obtain a coloring of a graph in the following lemma (which we use for Theorem~\ref{thm:subcubic_6}). \begin{lemma} \label{lemmalightedge} Let $G$ be a graph, let $l,k$ be two integers with $l\leq k$, and let $e=uv$ be an edge of $G$ with the property that (as above) $d(u)\leq l$ and $v$ has at most $l$ neighbours of degree $> l$. Then any $k$-intersection $r$-edge-coloring of $G-e$ can be extended to $G$ if $r\geq (l+1)\Delta -l(k-1)-1$. \end{lemma} \begin{proof} A coloring of $G-e$ can be extended to $e$ with the following observations: \begin{itemize} \item The color of $e$ must be different from at most $l-1$ colors used around $u$, and $u$ cannot have strictly more than $k$ colors in common with any of its neighbours (including $v$) as it has degree at most $l\leq k$ \item The color of $e$ has to be different from the (at most) $\Delta-1$ colors used around $v$. \item Assuming, in the worst case, that $v$ has exactly $k$ colors in common with each of its neighbours of degree $>l$, $e$ cannot be given a color already used around those (at most $\leq l$ vertices), which amounts to at most $l(\Delta-k)$ colors. \end{itemize} This list excludes a total of at most $(l-1) + (\Delta-1) + l(\Delta-k)\leq r-1$ colors, which ensures that one is available for $e$. \end{proof} \begin{corollary} \label{cor:ldegenerate} If $G$ is an $l$-degenerate graph and $k\geq l$, then $$\chik k(G)\leq (l+1)\Delta -l(k-1)-1$$ \end{corollary} A \emph{minimally $l$-connected graph} is a $l$-vertex-connected graph such that for any edge $e$, the subgraph $G-e$ is not $l$-vertex-connected. Trees being exactly the minimally 1-connected graphs, the $k$-intersection chromatic number of minimally 1-connected graphs is given by Proposition~\ref{Trees}. We show in the next theorem that for $k\geq 2$ the $k$-intersection chromatic number of a minimally 2-connected graph is almost determined by the formula of Corollary~\ref{cor:ldegenerate}. We omit the proof as it is very similar to the proof of previous theorem based on the following lemma proved in~\cite{CN12}. We recall that a minimally $l$-connected graph is an $l$-degenerate graph~\cite{M72} (see also~\cite[page 24]{EGT}). \begin{lemma}\cite{CN12} A minimally 2-connected graph contains an edge $uv$ such that $v$ has degree at most 2, and all but at most one of the neighbours of $u$ are also vertices of degree 2. \end{lemma} \begin{theorem}\label{Min2Conected} If $G$ is a minimally $2$-connected graph or a subgraph of such a graph, then for any $k$ with $2 \leq k \leq \Delta$ we have $ \kci(G) \leq max\{\Delta_e -k+1,\Delta\}$. \end{theorem} Note that this upper bound is just $1$ more than the general lower bound. For a cycle $C$ of odd length, we have $\chik 2(G)=3$, and thus this bound is attained for $k=2$. Recall that the case $k=1$ corresponds to strong edge-coloring, and this technique does not work for chordless graphs and 2-degenerate graphs since $k$ is smaller than the degeneracy. These cases are discussed in~\cite{CN12} where the authors show a linear upper bound. \bigskip A graph with $\Delta \leq 3$ is called \emph{subcubic}. For $k\geq 3$ the $\chik k(G)$ is the same as the chromatic index of $G$, thus if $\Delta=3$ then $\chik k(G)$ is either 3 or 4 (by Vizing's theorem). Determining whether 3 or 4 is the correct answer is a well-known NP-complete problem and it led to the study of snarks (see~\cite{CS2010} and its references). For $k=1$, determining the value of $\chik 1(G)$ is NP-Hard for subcubic graphs~\cite{thesepetru}, while $\chik 1(G)\leq 10$ for this class~\cite{horak1993,andersen1992}. Thus we consider the 2-intersection chromatic number for the class of subcubic graphs. We show below that the 2-intersection chromatic number of any subcubic graph is at most 6. We do not know if there is a subcubic graph of 2-intersection chromatic number equal to 6, though we have many examples for 5 (e.g. $K_{3,3}$). \begin{theorem} \label{thm:subcubic_6} Let $G$ be a subcubic graph. Then $\chik{2}(G)\leq 6$. \end{theorem} In order to show Theorem~\ref{thm:subcubic_6} we prove the following stronger statement: \begin{lemma} \label{lemma:subcubic_nice_coloring} Let $G$ be a subcubic graph. There exists a coloring $\phi$ using at most six colors, such that for every vertex $v$ of degree 2 with neighbours $u$ and $w$ of degree 3 (if any) either $\phi(uv)\notin \phi(w)$ or $\phi(wv)\notin \phi(u)$. \end{lemma} \begin{proof} By contradiction. Suppose the statement of the lemma is not true and let $G$ be a counterexample minimizing $|V(G)|$. Thus $G$ is connected. Let $v$ be a vertex of $G$ and let $\phi$ be a 2-intersection 6-edge-coloring of $G-v$ satisfying the conditions of the Lemma. Observe that if applied to $G$, the coloring $\phi$ could violate the conditions of the Lemma. This could happen only in the following particular situation: $v$ has a neighbour $u_1$ of degree 3 with $u_2$ and $u_3$ being the other two neighbours of $u_1$; $u_2$ is a vertex of degree 2 and $u_3$ is a vertex of degree 3. If one applies $\phi$ to $G$, then vertex $u_2$ might not satisfy the statement of the Lemma. However, in this case, it is possible to recolor the edge $u_2u_1$ with another color in order to obtain a valid partial coloring of $G$ satisfying the statement of the Lemma. Therefore, we will assume that, when applied to $G$, the coloring $\phi$ remains valid and thus the only remaining edges to color are those incident to $v$. By the minimality of $G$, $v$ cannot be of degree 1, as otherwise $\phi$ could be easily extended to $G$. Hence $v$ has degree at least 2. %\input{6coldegree2.tex} \pgfdeclarelayer{edgelayer} \pgfdeclarelayer{nodelayer} \pgfsetlayers{edgelayer,nodelayer,main} \begin{figure}[!ht] \centering \begin{tikzpicture}[join=bevel,inner sep=0.5mm,scale=0.7] \def\dec{0.35}; \def\de{0.4}; \begin{pgfonlayer}{nodelayer} \node [draw,circle,fill=white] (0) at (3.25, 2.5) {$v$}; \node [draw,circle,fill=white] (1) at (-1.75, -0.25) {$u_2$}; \node [draw,circle,fill=white] (2) at (1.25, -0.25) {$u_3$}; \node [draw,circle,fill=white] (3) at (5.25, -0.25) {$w_2$}; \node [draw,circle,fill=white] (4) at (8.25, -0.25) {$w_3$}; \node [draw,circle,fill=white] (5) at (-2.5, -2.5) {$u_4$}; \node [draw,circle,fill=white] (6) at (-1, -2.5) {$u_5$}; \node [draw,circle,fill=white] (7) at (0.5, -2.5) {$u_6$}; \node [draw,circle,fill=white] (8) at (2, -2.5) {$u_7$}; \node [draw,circle,fill=white] (9) at (4.5, -2.5) {$w_4$}; \node [draw,circle,fill=white] (10) at (6, -2.5) {$w_5$}; \node [draw,circle,fill=white] (11) at (7.5, -2.5) {$w_6$}; \node [draw,circle,fill=white] (12) at (9, -2.5) {$w_7$}; \node [draw,circle,fill=white] (13) at (-0.25, 1.5) {$u_1$}; \node [draw,circle,fill=white] (14) at (6.75, 1.5) {$w_1$}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [-] (13) to (1); \draw [-] (1) to (5); \draw [-] (6) to (1); \draw [-] (7) to (2); \draw [-] (2) to (13); \draw [-] (2) to (8); \draw [-] (9) to (3); \draw [-] (3) to (14); \draw [-] (14) to (4); \draw [-] (4) to (11); \draw [-] (4) to (12); \draw [-] (10) to (3); \draw [-,dashed] (14) to (0); \draw [-,dashed] (0) to (13); \end{pgfonlayer} \end{tikzpicture}\caption{Example of vertex of degree 2} \label{fig:subcubic_2vertex} \end{figure} First, let us suppose that there exists a vertex $v$ of degree 2. Note that since $G$ is connected it is also 2-degenerate. We use the labeling of Figure~\ref{fig:subcubic_2vertex} to label vertices around $v$, but we point out that different vertices of the figure may represent the same vertex in the graph. We count the number of colors we cannot use at $vu_1$. To have a proper edge-coloring, $\phi(u_1u_2)$ and $\phi(u_1u_3)$ are forbidden. Any proper edge-coloring would be a 2-intersection edge-coloring unless either $\phi(u_1u_2) \in \{\phi(u_3u_6), \phi(u_3u_7)\}$, or $\phi(u_1u_3) \in \{\phi(u_2u_4), \phi(u_2u_5)\}$. However by our assumption, only one of these two cases can happen, say $\phi(u_1u_3)=\phi(u_2u_4)$, in which case the color $\phi(u_2u_5)$ is also forbidden at $vu_1$. Thus in general we have at least three colors available for $vu_1$. Let $\{1,2,3\}$ be this set of three colors. Similarly there are three colors available at $vw_1$ and let $\{\alpha,\beta,\omega\}$ be this set of three colors. Let us color $vu_1$ by 1. If $\{\alpha,\beta,\omega\} \neq \{1, \phi(u_1u_2), \phi(u_1u_3)\}$, then we have a color for $vw_1$ which satisfies the condition of the lemma. Otherwise, note $\alpha=1,\beta=\phi(u_1u_2),\omega=\phi(u_1u_3)$ and color $vw_1$ with $\alpha=1$ and $vu_1$ with 2 (as $2\notin \{\phi(u_1u_2), \phi(u_1u_3)\}$). Therefore, every vertex is of degree 3. This time we use the labeling of the neighbourhood of $v$ given in Figure~\ref{fig:subcubic_precol}. Again different vertices of the figure may represent the same vertex in the graph, in which case the proof is even simpler. Let $\alpha,\beta,\omega$ be the respective colors of edges $u_1u_2$, $w_1w_2$ and $t_1t_2$. Depending on the number of distinct colors among $\alpha,\beta,\omega$ we consider three cases. \pgfdeclarelayer{edgelayer} \pgfdeclarelayer{nodelayer} \pgfsetlayers{edgelayer,nodelayer,main} \begin{figure}[!h] \centering \begin{tikzpicture}[join=bevel,inner sep=0.5mm,scale=0.7] \begin{pgfonlayer}{nodelayer} \node [draw,circle,fill=white] (0) at (0, 3) {$v$}; \node [draw,circle,fill=white] (1) at (-6, -0) {$u_1$}; \node [draw,circle,fill=white] (2) at (-7, -2) {$u_2$}; \node [draw,circle,fill=white] (3) at (-5, -2) {$u_3$}; \node [draw,circle,fill=white] (4) at (-9, -4) {$u_4$}; \node [draw,circle,fill=white] (5) at (-7, -4) {$u_5$}; \node [draw,circle,fill=white] (6) at (-5, -4) {$u_6$}; \node [draw,circle,fill=white] (7) at (-3, -4) {$u_7$}; \node [draw,circle,fill=white] (8) at (0, -0) {$w_1$}; \node [draw,circle,fill=white] (9) at (-1, -2) {$w_2$}; \node [draw,circle,fill=white] (10) at (1, -2) {$w_3$}; \node [draw,circle,fill=white] (11) at (-2, -4) {$w_4$}; \node [draw,circle,fill=white] (12) at (0, -4) {$w_5$}; \node [draw,circle,fill=white] (13) at (1, -4) {$w_6$}; \node [draw,circle,fill=white] (14) at (3, -4) {$w_7$}; \node [draw,circle,fill=white] (15) at (6, -0) {$t_1$}; \node [draw,circle,fill=white] (16) at (5, -2) {$t_2$}; \node [draw,circle,fill=white] (17) at (7, -2) {$t_3$}; \node [draw,circle,fill=white] (18) at (4, -4) {$t_4$}; \node [draw,circle,fill=white] (19) at (6, -4) {$t_5$}; \node [draw,circle,fill=white] (20) at (7, -4) {$t_6$}; \node [draw,circle,fill=white] (21) at (9, -4) {$t_7$}; \node [draw,fill=white] (22) at (-7, -0.75) {$\alpha$}; %\node [draw,fill=white] (23) at (-5, -0.75) {$b$}; \node [draw,fill=white] (24) at (-1, -1) {$\beta$}; %\node [draw,fill=white] (25) at (1, -1) {$h$}; \node [draw,fill=white] (26) at (5, -1) {$\omega$}; %\node [draw,fill=white] (27) at (7, -1) {$n$}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [-,dashed] (0) to (8); \draw [-,dashed] (0) to (1); \draw [-] (1) to (2); \draw [-] (2) to (4); \draw [-] (2) to (5); \draw [-] (1) to (3); \draw [-] (3) to (6); \draw [-] (3) to (7); \draw [-] (11) to (9); \draw [-] (9) to (12); \draw [-] (8) to (9); \draw [-] (8) to (10); \draw [-] (10) to (13); \draw [-] (10) to (14); \draw [-,dashed] (0) to (15); \draw [-] (15) to (16); \draw [-] (16) to (18); \draw [-] (16) to (19); \draw [-] (15) to (17); \draw [-] (17) to (20); \draw [-] (17) to (21); \end{pgfonlayer} \end{tikzpicture} \caption{The precoloring} \label{fig:subcubic_precol} \end{figure} \begin{itemize} \item Suppose $\alpha=\beta=\omega$. Since $\phi$ satisfies the condition of the lemma, just as in the previous case there are at least three colors available for each of $vu_1$, $vw_1$ and $vt_1$. Thus we can pick one distinct color for each, and since $\alpha$ is forbidden for all three the coloring is 2-intersection for all these three edges. \item We have $\alpha=\beta\neq\omega$. Moreover, we know that $\alpha\neq \phi(t_1t_3)$. Therefore, without loss of generality we can assume that $\alpha=\beta=1$, $\omega=2$ and $\phi(t_1t_3)=3$. We pick a color for $vt_1$ different from $\alpha=\beta$ and since it must be different from $\phi(t_1t_2)$ and $\phi(t_1t_3)$, we can say this color is 4. Then we color successively $vw_1$ and $vu_1$ by choosing each time a color such that $\phi$ remains a proper edge-coloring. Now, since $G$ is a counterexample, $\phi$ cannot be a 2-intersection coloring. The only possible conflict is that the colors we have chosen for $vw_1$ and $vu_1$ are respectively 2 and 3. Hence we have the following set of available colors for $vu_1$ and $vw_1$: $\{2,3,4\}$. Also, recall that the other two colors which were initially available for $vt_1$ can be neither 2 nor 3 (because $t_1t_2$ and $t_1t_3$ are colored 2 and 3 respectively). Hence we color $vu_1$ with 4, $vw_1$ with 2 and recolor $vt_1$ with a color different from 4. We are done. \item Last case is when $|\{\alpha,\beta,\omega\}|=3$. More generally, in $G-v$ the sets $\phi(u_1)$, $\phi(w_1)$ and $\phi(t_1)$ are pairwise disjoint and thus we can fix $\phi(u_1u_2)=1$, $\phi(u_1u_3)=2$, $\phi(w_1w_2)=3$, $\phi(w_1w_3)=4$, $\phi(t_1t_2)=5$ and $\phi(t_1t_3)=6$. As in the previous cases we color successively $vt_1$ and $vw_1$ such that there are no conflicts. It remains to color $vu_1$. We pick a color $\zeta\notin\{\phi(vt_1),\phi(vw_1),\phi(u_1u_2),\phi(u_1u_3)\}$ for it such that the coloring of the subgraph $G-\{vw_1,vt_1\}$ is a 2-intersection edge-coloring (note that this is possible due to the hypothesis on $G-v$). Since $G$ is a counterexample the obtained proper edge-coloring must not be a 2-intersection coloring. Therefore, without loss of generality we can assume that $\zeta=5$ and $\phi(vw_1)=6$. Observe that this is the only possible conflict. If it is possible to replace $\zeta$ by some other color then we would be done. Hence the set of available colors for $vu_1$ is $\{5,6,\phi(vt_1)\}$. Assume $\gamma=\phi(vt_1)$ (thus $\gamma\notin\{1,2\}$). Recall that initially we had three colors for edge $vt_1$, say $\{\gamma,\nu,\mu\}$, and these colors cannot be neither 5 nor 6. Therefore, we have $\gamma\in\{3,4\}$ and we assign $\phi(vu_1)=\gamma$ and choose for $vt_1$ color $\nu\notin\{3,4\}$. The obtained coloring is a valid 2-intersection 6-edge-coloring. \end{itemize} Thus no such counterexample exists. \end{proof} \section{Complete graphs} \label{sec:complete} Determining $\chik k(K_n)$ turns out to be more of a combinatorial set theory problem. While we are not able to reduce it to a simple expression depending on $n$ and $k$, we can understand its asymptotic behaviour to some extent: the key tool in our attempt is a lemma of Corr\'adi (cf. Lemma~\ref{Corradi}) which provides an asymptotically tight lower bound for odd values of $k$. This lemma can then be improved and adapted to our needs in order to yield another asymptotically tight lower bound for even values of $k$. It turns out that for a fixed $k$, the $k$-intersection chromatic index of $K_n$ grows like a linear function of the number $\binom{n}{2}$ of edges. To this end we want to find the constant $c_k$ such that $\chik k(K_n) = c_k \binom{n}{2}+O(n)$. We now show how a coloring of a small complete graph can be used to generate colorings of arbitrarily large ones, and hence produce an asymptotic upper bound on $\chik k(K_n)$. For this we use the following decomposition theorem: \begin{theorem}[Wilson \cite{W75}, see also IV.3.7 in \cite{CD}] For a given integer $p$ and sufficiently large integer $n$, the edge set of $K_n$ can be partitioned into copies of $K_p$ if and only if $\binom p 2$ divides $\binom n 2$ and $p-1$ divides $n-1$. \end{theorem} Let us now suppose that $\chik k(K_p) = c_k \binom{p}{2}$ holds for some integer $p$, and let $n$ be chosen to satisfy the conditions of Wilson's theorem. We can partition edges of $K_n$ into copies of $K_p$ as the theorem claims, and give a $k$-intersection edge-coloring of each $K_p$ with a distinct set of $\chik k(K_p) = c_k {\binom{p}{2}}$ colors. This results in a $k$-intersection edge-coloring of $K_n$ with $c_k \binom{n}{2}$ colors. The first lower bound we obtain is a consequence of the following lemma. \begin{lemma} [Corr\'adi~\cite{C69}, see also p.23 of \cite{jukna}] \label{Corradi} Let $A_1, A_2, \ldots, A_n$ be $r$-element sets whose union is $X$. If $|A_i\cap A_j| \le k$ for all $i \neq j$, then $|X| \ge \frac{r^2 n}{r+(n-1)k}$. \end{lemma} Let $K_n$ be $k$-intersection edge-colored with $\chik k(K_n)$ colors. Let $A_i$ be the set of colors used at edges incident to vertex $i$. Then each $A_i$ is an $(n-1)$-subset of the set of colors used and $|A_i\cap A_j| \le k$ is satisfied because the coloring is a $k$-intersection edge-coloring. Applying the lemma we have: \begin{corollary} \label{lowercomplete} For any values of $k$ and $n$ we have $\chik k(K_n) \geq \frac{2}{k+1} \binom{n}{2}$. \end{corollary} $K_{k+1}$ is $k$-edge-colorable when $k$ is odd, and any proper edge-coloring of $K_{k+1}$ is a $k$-intersection edge-coloring as all vertices are of degree $k$: as a result we have $\chik k(K_{k+1}) = \frac{2}{k+1} \binom{k+1}{2}$. Consequently, from our construction based on Wilson's theorem: \begin{corollary} \label{BestBoundForOddk} \label{corcompleteodd} For odd values of $k$ we have $\chik k(K_n) = \frac{2}{k+1} \binom{n}{2}+O(n)$. Besides, $\chik k(K_n) = \frac{2}{k+1}\binom{n}{2}$ for infinitely many values of $n$. \end{corollary} For even values of $k$ the lower bound of Corollary~\ref{lowercomplete} is never tight. An improved lower bound in this case is given in the following theorem. \begin{theorem} \label{thm:complete_lower_evenk} For even values of $k$ we have $\chik k(K_n)\geq \frac{2k+2}{k^2+2k}\binom{n}{2}$. \end{theorem} \begin{proof} Assume that $K_n$ is $k$-intersection edge-colored with a set $C$ of colors of cardinality $r$. Build a hypergraph $\mathcal H$ whose vertex set is $C$, and whose hyperedges are -- for each vertex $v$ of $K_n$ -- the set of colors incident to $v$. As a consequence, $\mathcal H$ has $n$ edges of cardinality $n-1$. For a vertex $c \in C $ of $\mathcal H$ let $d_{\mathcal H}(c)$ be the degree of $c$ in $\mathcal H$. We obtain the following upper bound on $\sum_{c\in C}d_{\mathcal H}(c)^2$. \begin{align*} \sum_{c\in C}d_{\mathcal H}(c)^2 & =\sum_{e\in\mathcal H}\sum_{e'\in\mathcal H}|e\cap e'|\\ &=\sum_{e\in\mathcal H} \Big( |e| + \sum_{\substack{e'\in\mathcal H\\ e\neq e'}}|e\cap e'|\Big)\\ &\leq\sum_{e\in\mathcal H} \Big( (n-1) + k(n-1)\Big)\\ &= (k+1)n(n-1)\\ &= 2(k+1) \binom{n}{2}\\ \end{align*} For a given $c\in C$ let $R(c)$ be the number of edges of $K_n$ colored with $c$. Since we are working with proper edge-coloring we have $R(c)= \frac{1}{2} d_{\mathcal H}(c)$. Replacing these values in the previous inequality we have \begin{align} \sum _{c\in C}R(c)^2\leq \frac{k+1}{2} \binom n 2 \label{ineq:upper_bound} \end{align} We are now missing a lower bound for the left side of this inequality, and for this we can use the Cauchy-Schwarz inequality. Indeed, \begin{align} \sum _{c\in C}R(c)^2 &\geq |C|\left(\frac{\sum_{c\in C}\frac 1 2 d_{\mathcal H}(c)}{| C|}\right)^2=|C|\left(\frac{\binom{n}{2}}{| C|}\right)^2 \label{ineq:lower_bound_Cauchy_Schwarz} \end{align} Together with the previous formula, this yields the inequality $| C|\geq \frac{2}{k+1} \binom n 2$ (i.e. Corollary~\ref{lowercomplete}), and the proof up to this point is the one of Corr\'adi's lemma as found in \cite{jukna}. Note that inequality (\ref{ineq:lower_bound_Cauchy_Schwarz}) is tight if and only if $R(c)=\binom{n}{2}/{|C|}$ for all $c\in C$. Substituting this value for each R(c) implies $R(c)=\frac{k+1}{2}$. Therefore when $k$ is even the inequality cannot be tight as $\frac{k+1}{2}$ is not an integer. In the following we show how to improve inequality~(\ref{ineq:lower_bound_Cauchy_Schwarz}) by arguing that our variables must be integers. %This improvement is based on the fact that $R(c)$ is an integer. Since $\sum _{c\in C}R(c)=\binom{n}{2}$, the sum $\sum _{c\in C}R(c)^2$ is minimized when $|R(c)-R(c')|\leq 1$ for any two colors $c,c'\in C$. Let this minimum be $f(r)$ where $r=| C|$. For integers $p$ and $q$ we use the notation $p \% q$ to denote the remainder in the division of $p$ by $q$. By what we have just said, $f(r)$ defined by $$ f(r)= \underbrace{\left(r - \binom n 2 \%r\right)}_{{\text{number of colors }c}\atop{\text{ such that }R(c)=\left\lfloor {\binom n 2}/r\right\rfloor}} \left\lfloor \frac{\binom{n}{2}}{r}\right\rfloor^2+ \underbrace{\left(\binom n 2\%r\right)}_{{\text{number of colors }c}\atop{\text{ such that }R(c)=\left\lfloor {\binom n 2}/r\right\rfloor}+1} \left(\left\lfloor \frac{\binom n 2}{r}\right\rfloor+1\right)^2$$ is a lower bound for $\sum _{c\in C}R(c)^2$ and we would like to find a better lower bound for $f(r)$. Since we already know that $ r\geq \frac{2}{k+1} \binom n 2$ we claim that $f(r-1) > f(r)$ when $n$ is large enough. To see this, recall that $f(r)=\sum _{c\in C}R(c)^2$ where $R(c)$'s in the sum differ at most by 1. Thus one can obtain $f(r-1)$ from $f(r)$ by removing the smaller of $R(c)$'s, say $R(c_1)$ from the sum and distributing it evenly among the rest starting with the smaller ones. Note that since $r$ is large with respect to $R(c_1)$, in this distribution exactly $R(c_1)$ of $R(c)$'s are increased by 1. Thus to obtain $f(r-1)$ from $f(r)$ one subtracts $R(c_1)^2$ and adds a minimum of $R(c_1)\times 2R(c_1)$. Thus $f(r-1)>f(r)$, and therefore $f(r)$ is a strictly decreasing function of $r$ for $ r\geq \frac{2}{k+1} \binom n 2$. If we find a value of $r_0\geq \frac{2}{k+1} \binom n 2$ such that $f(r_0)\geq\frac{k+1}{2} \binom n 2$, then we would conclude that $\chik k(K_n) \geq r_0$. To see this, suppose $K_n$ admits a coloring with $|C|=r f(r_0) \geq \frac{k+1}{2} \binom n 2$. This contradicts inequality~(\ref{ineq:upper_bound}). Therefore, to complete the proof of the theorem it is enough to show that for $r_0=\left\lceil\frac{2k+2}{k^2+2k}\binom{n}{2}\right\rceil$ we have $f(r_0)\geq\frac{k+1}{2} \binom n 2$. We give the main idea of the proof when the fraction $\frac{2k+2}{k^2+2k}\binom{n}{2}$ is an integer. First note that $\frac{2}{k+1}\binom{n}{2}\leq r_0 < \frac{2}{k} \binom n 2$. Thus $ \binom n 2 \% r_0 =\frac{1}{k+2}\binom{n}{2}$ and $\left\lfloor \frac{\binom{n}{2}}{r_0}\right\rfloor = \frac{k}{2}$. So $$f(r_0)=\left(\frac{2k+2}{k^2+2k}-\frac{1}{k+2}\right)\binom{n}{2} \left(\frac{k}{2}\right)^2 + \frac{1}{k+2}\binom{n}{2}\left(\frac{k}{2}+1\right)^2 = \frac{2k+2}{k^2+2k}\binom{n}{2}$$. \end{proof} We believe that given an even $k$ the lower bound of Theorem~\ref{thm:complete_lower_evenk} is tight for infinitely many values of $n$. To this end, considering Wilson's theorem it would be enough to prove that the equality holds for at least one value of $n$. \begin{conjecture} For each even value of $k$, there exists an integer $n$ such that $\chik k(K_n)=\frac{2k+2}{k^2+2k}\binom{n}{2}$. \end{conjecture} Indeed, for both $k=2$ and $k=4$, choosing $n=9$ works. \begin{theorem} We have $\chik 2(K_n) = \frac{3}{4} \binom n 2+O(n)$ and $\chik 4(K_n) =\frac{5}{12} \binom n 2+O(n)$. Furthermore, the equalities $\chik 2(K_n) = \frac{3}{4} \binom n 2$ and $\chik 4(K_n)=\frac{5}{12} \binom n 2$ hold for infinitely many values of $n$. \end{theorem} \begin{proof} The colorings are produced from the construction based on Wilson's Theorem, and the two colorings of $K_9$ given in Figures~\ref{fig:k9coloring} and \ref{fig:i4k9coloring} which prove that $\chik 2(K_9)=\frac{3}{4} \binom 9 2=27$ and $\chik 4(K_9)=\frac{5}{12} \binom 9 2=15$. Note that Figure~\ref{fig:k9coloring} only shows a 2-intersection 9-edge-coloring of $C_9^2$, but assigning a unique color to each missing edge would result in a 2-intersection 27-edge-coloring of $K_9$. \end{proof} \begin{center} %\input{col2intk9.tex} \begin{figure}[!ht] \centering \begin{tikzpicture}[scale=3] \draw[color=gray] plot [smooth, tension=1] coordinates {(0.766cm,0.643cm) (1.00cm,0.000cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(0.174cm,0.985cm) (1.00cm,0.000cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(0.174cm,-0.985cm) (1.00cm,0.000cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(0.766cm,-0.643cm) (1.00cm,0.000cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(0.174cm,0.985cm) (0.766cm,0.643cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(-0.500cm,0.866cm) (0.766cm,0.643cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(0.766cm,-0.643cm) (0.766cm,0.643cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(-0.500cm,0.866cm) (0.174cm,0.985cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(-0.940cm,0.342cm) (0.174cm,0.985cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(-0.940cm,0.342cm) (-0.500cm,0.866cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(-0.940cm,-0.342cm) (-0.500cm,0.866cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(-0.940cm,-0.342cm) (-0.940cm,0.342cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(-0.500cm,-0.866cm) (-0.940cm,0.342cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(-0.500cm,-0.866cm) (-0.940cm,-0.342cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(0.174cm,-0.985cm) (-0.940cm,-0.342cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(0.174cm,-0.985cm) (-0.500cm,-0.866cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(0.766cm,-0.643cm) (-0.500cm,-0.866cm)}; \draw[color=gray] plot [smooth, tension=1] coordinates {(0.766cm,-0.643cm) (0.174cm,-0.985cm)}; \node (all) at (0.883cm,0.321cm) {$3$}; \node (all) at (0.587cm,0.492cm) {$1$}; \node (all) at (0.587cm,-0.492cm) {$0$}; \node (all) at (0.883cm,-0.321cm) {$2$}; \node (all) at (0.470cm,0.814cm) {$6$}; \node (all) at (0.133cm,0.754cm) {$2$}; \node (all) at (0.766cm,0) {$4$}; \node (all) at (-0.163cm,0.925cm) {$7$}; \node (all) at (-0.383cm,0.663cm) {$3$}; \node (all) at (-0.720cm,0.604cm) {$5$}; \node (all) at (-0.720cm,0.262cm) {$6$}; \node (all) at (-0.940cm,0) {$8$}; \node (all) at (-0.720cm,-0.262cm) {$7$}; \node (all) at (-0.720cm,-0.604cm) {$0$}; \node (all) at (-0.383cm,-0.663cm) {$5$}; \node (all) at (-0.163cm,-0.925cm) {$4$}; \node (all) at (0.133cm,-0.754cm) {$8$}; \node (all) at (0.470cm,-0.814cm) {$1$}; \draw (1.00cm,0.000cm) node[fill=black, shape=circle, scale=.5] (v1) {}; \draw (0.766cm,0.643cm) node[fill=black, shape=circle, scale=.5] (v1) {}; \draw (0.174cm,0.985cm) node[fill=black, shape=circle, scale=.5] (v2) {}; \draw (-0.500cm,0.866cm) node[fill=black, shape=circle, scale=.5] (v3) {}; \draw (-0.940cm,0.342cm) node[fill=black, shape=circle, scale=.5] (v4) {}; \draw (-0.940cm,-0.342cm) node[fill=black, shape=circle, scale=.5] (v5) {}; \draw (-0.500cm,-0.866cm) node[fill=black, shape=circle, scale=.5] (v6) {}; \draw (0.174cm,-0.985cm) node[fill=black, shape=circle, scale=.5] (v7) {}; \draw (0.766cm,-0.643cm) node[fill=black, shape=circle, scale=.5] (v8) {}; \node [shift={(-20:.8cm)}] at (v8) {\scriptsize \{1,2,4,8\}}; \node [shift={(20:.8cm)}] at (v1) {\scriptsize \{2,3,4,6\}}; \node [shift={(90:.3cm)}] at (v2) {\scriptsize \{1,3,6,7\}}; \node [shift={(120:.4cm)}] at (v3) {\scriptsize \{2,5,6,7\}}; \node [shift={(180:.8cm)}] at (v4) {\scriptsize \{3,5,7,8\}}; \node [shift={(-150:.7cm)}] at (v5) {\scriptsize \{0,5,6,8\}}; \node [shift={(-120:.45cm)}] at (v6) {\scriptsize \{0,4,7,8\}}; \node [shift={(-90:.4cm)}] at (v7) {\scriptsize \{0,1,4,5\}}; \end{tikzpicture} \caption{A $2$-intersection edge-coloring of $C_9^2$ with 9 colors.} \label{fig:k9coloring} \end{figure} \begin{figure}[!ht] \begin{center} \begin{tikzpicture} \draw (5.0, 0.0) -- (3.83022221559489, 3.2139380484326963); \draw (5.0, 0.0) -- (0.8682408883346521, 4.92403876506104); \draw (5.0, 0.0) -- (-2.499999999999999, 4.330127018922194); \draw (5.0, 0.0) -- (-4.698463103929542, 1.7101007166283444); \draw (5.0, 0.0) -- (-4.698463103929543, -1.7101007166283433); \draw (5.0, 0.0) -- (-2.500000000000002, -4.330127018922192); \draw (5.0, 0.0) -- (0.8682408883346499, -4.924038765061041); \draw (5.0, 0.0) -- (3.830222215594889, -3.213938048432698); \draw (3.83022221559489, 3.2139380484326963) -- (0.8682408883346521, 4.92403876506104); \draw (3.83022221559489, 3.2139380484326963) -- (-2.499999999999999, 4.330127018922194); \draw (3.83022221559489, 3.2139380484326963) -- (-4.698463103929542, 1.7101007166283444); \draw (3.83022221559489, 3.2139380484326963) -- (-4.698463103929543, -1.7101007166283433); \draw (3.83022221559489, 3.2139380484326963) -- (-2.500000000000002, -4.330127018922192); \draw (3.83022221559489, 3.2139380484326963) -- (0.8682408883346499, -4.924038765061041); \draw (3.83022221559489, 3.2139380484326963) -- (3.830222215594889, -3.213938048432698); \draw (0.8682408883346521, 4.92403876506104) -- (-2.499999999999999, 4.330127018922194); \draw (0.8682408883346521, 4.92403876506104) -- (-4.698463103929542, 1.7101007166283444); \draw (0.8682408883346521, 4.92403876506104) -- (-4.698463103929543, -1.7101007166283433); \draw (0.8682408883346521, 4.92403876506104) -- (-2.500000000000002, -4.330127018922192); \draw (0.8682408883346521, 4.92403876506104) -- (0.8682408883346499, -4.924038765061041); \draw (0.8682408883346521, 4.92403876506104) -- (3.830222215594889, -3.213938048432698); \draw (-2.499999999999999, 4.330127018922194) -- (-4.698463103929542, 1.7101007166283444); \draw (-2.499999999999999, 4.330127018922194) -- (-4.698463103929543, -1.7101007166283433); \draw (-2.499999999999999, 4.330127018922194) -- (-2.500000000000002, -4.330127018922192); \draw (-2.499999999999999, 4.330127018922194) -- (0.8682408883346499, -4.924038765061041); \draw (-2.499999999999999, 4.330127018922194) -- (3.830222215594889, -3.213938048432698); \draw (-4.698463103929542, 1.7101007166283444) -- (-4.698463103929543, -1.7101007166283433); \draw (-4.698463103929542, 1.7101007166283444) -- (-2.500000000000002, -4.330127018922192); \draw (-4.698463103929542, 1.7101007166283444) -- (0.8682408883346499, -4.924038765061041); \draw (-4.698463103929542, 1.7101007166283444) -- (3.830222215594889, -3.213938048432698); \draw (-4.698463103929543, -1.7101007166283433) -- (-2.500000000000002, -4.330127018922192); \draw (-4.698463103929543, -1.7101007166283433) -- (0.8682408883346499, -4.924038765061041); \draw (-4.698463103929543, -1.7101007166283433) -- (3.830222215594889, -3.213938048432698); \draw (-2.500000000000002, -4.330127018922192) -- (0.8682408883346499, -4.924038765061041); \draw (-2.500000000000002, -4.330127018922192) -- (3.830222215594889, -3.213938048432698); \draw (0.8682408883346499, -4.924038765061041) -- (3.830222215594889, -3.213938048432698); \path (5.0, 0.0) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (3.83022221559489, 3.2139380484326963); \path (5.0, 0.0) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (0.8682408883346521, 4.92403876506104); \path (5.0, 0.0) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-2.499999999999999, 4.330127018922194); \path (5.0, 0.0) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-4.698463103929542, 1.7101007166283444); \path (5.0, 0.0) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-4.698463103929543, -1.7101007166283433); \path (5.0, 0.0) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-2.500000000000002, -4.330127018922192); \path (5.0, 0.0) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (0.8682408883346499, -4.924038765061041); \path (5.0, 0.0) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (3.830222215594889, -3.213938048432698); \path (3.83022221559489, 3.2139380484326963) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (0.8682408883346521, 4.92403876506104); \path (3.83022221559489, 3.2139380484326963) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-2.499999999999999, 4.330127018922194); \path (3.83022221559489, 3.2139380484326963) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-4.698463103929542, 1.7101007166283444); \path (3.83022221559489, 3.2139380484326963) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-4.698463103929543, -1.7101007166283433); \path (3.83022221559489, 3.2139380484326963) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-2.500000000000002, -4.330127018922192); \path (3.83022221559489, 3.2139380484326963) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (0.8682408883346499, -4.924038765061041); \path (3.83022221559489, 3.2139380484326963) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (3.830222215594889, -3.213938048432698); \path (0.8682408883346521, 4.92403876506104) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-2.499999999999999, 4.330127018922194); \path (0.8682408883346521, 4.92403876506104) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-4.698463103929542, 1.7101007166283444); \path (0.8682408883346521, 4.92403876506104) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-4.698463103929543, -1.7101007166283433); \path (0.8682408883346521, 4.92403876506104) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-2.500000000000002, -4.330127018922192); \path (0.8682408883346521, 4.92403876506104) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (0.8682408883346499, -4.924038765061041); \path (0.8682408883346521, 4.92403876506104) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (3.830222215594889, -3.213938048432698); \path (-2.499999999999999, 4.330127018922194) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-4.698463103929542, 1.7101007166283444); \path (-2.499999999999999, 4.330127018922194) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-4.698463103929543, -1.7101007166283433); \path (-2.499999999999999, 4.330127018922194) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-2.500000000000002, -4.330127018922192); \path (-2.499999999999999, 4.330127018922194) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (0.8682408883346499, -4.924038765061041); \path (-2.499999999999999, 4.330127018922194) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (3.830222215594889, -3.213938048432698); \path (-4.698463103929542, 1.7101007166283444) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-4.698463103929543, -1.7101007166283433); \path (-4.698463103929542, 1.7101007166283444) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-2.500000000000002, -4.330127018922192); \path (-4.698463103929542, 1.7101007166283444) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (0.8682408883346499, -4.924038765061041); \path (-4.698463103929542, 1.7101007166283444) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (3.830222215594889, -3.213938048432698); \path (-4.698463103929543, -1.7101007166283433) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (-2.500000000000002, -4.330127018922192); \path (-4.698463103929543, -1.7101007166283433) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (0.8682408883346499, -4.924038765061041); \path (-4.698463103929543, -1.7101007166283433) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (3.830222215594889, -3.213938048432698); \path (-2.500000000000002, -4.330127018922192) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (0.8682408883346499, -4.924038765061041); \path (-2.500000000000002, -4.330127018922192) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (3.830222215594889, -3.213938048432698); \path (0.8682408883346499, -4.924038765061041) -- node [pos = 0.15, circle, fill=white, scale=.9] {} node [pos = 0.85, circle, fill=white, scale=.9] {} (3.830222215594889, -3.213938048432698); \path (5.0, 0.0) -- node [pos = 0.15,scale=.7] {$3$} node [pos = 0.85,scale=.7] {$3$} (3.83022221559489, 3.2139380484326963); \path (5.0, 0.0) -- node [pos = 0.15,scale=.7] {$7$} node [pos = 0.85,scale=.7] {$7$} (0.8682408883346521, 4.92403876506104); \path (5.0, 0.0) -- node [pos = 0.15,scale=.7] {$6$} node [pos = 0.85,scale=.7] {$6$} (-2.499999999999999, 4.330127018922194); \path (5.0, 0.0) -- node [pos = 0.15,scale=.7] {$11$} node [pos = 0.85,scale=.7] {$11$} (-4.698463103929542, 1.7101007166283444); \path (5.0, 0.0) -- node [pos = 0.15,scale=.7] {$12$} node [pos = 0.85,scale=.7] {$12$} (-4.698463103929543, -1.7101007166283433); \path (5.0, 0.0) -- node [pos = 0.15,scale=.7] {$13$} node [pos = 0.85,scale=.7] {$13$} (-2.500000000000002, -4.330127018922192); \path (5.0, 0.0) -- node [pos = 0.15,scale=.7] {$1$} node [pos = 0.85,scale=.7] {$1$} (0.8682408883346499, -4.924038765061041); \path (5.0, 0.0) -- node [pos = 0.15,scale=.7] {$5$} node [pos = 0.85,scale=.7] {$5$} (3.830222215594889, -3.213938048432698); \path (3.83022221559489, 3.2139380484326963) -- node [pos = 0.15,scale=.7] {$4$} node [pos = 0.85,scale=.7] {$4$} (0.8682408883346521, 4.92403876506104); \path (3.83022221559489, 3.2139380484326963) -- node [pos = 0.15,scale=.7] {$13$} node [pos = 0.85,scale=.7] {$13$} (-2.499999999999999, 4.330127018922194); \path (3.83022221559489, 3.2139380484326963) -- node [pos = 0.15,scale=.7] {$14$} node [pos = 0.85,scale=.7] {$14$} (-4.698463103929542, 1.7101007166283444); \path (3.83022221559489, 3.2139380484326963) -- node [pos = 0.15,scale=.7] {$7$} node [pos = 0.85,scale=.7] {$7$} (-4.698463103929543, -1.7101007166283433); \path (3.83022221559489, 3.2139380484326963) -- node [pos = 0.15,scale=.7] {$12$} node [pos = 0.85,scale=.7] {$12$} (-2.500000000000002, -4.330127018922192); \path (3.83022221559489, 3.2139380484326963) -- node [pos = 0.15,scale=.7] {$0$} node [pos = 0.85,scale=.7] {$0$} (0.8682408883346499, -4.924038765061041); \path (3.83022221559489, 3.2139380484326963) -- node [pos = 0.15,scale=.7] {$9$} node [pos = 0.85,scale=.7] {$9$} (3.830222215594889, -3.213938048432698); \path (0.8682408883346521, 4.92403876506104) -- node [pos = 0.15,scale=.7] {$9$} node [pos = 0.85,scale=.7] {$9$} (-2.499999999999999, 4.330127018922194); \path (0.8682408883346521, 4.92403876506104) -- node [pos = 0.15,scale=.7] {$1$} node [pos = 0.85,scale=.7] {$1$} (-4.698463103929542, 1.7101007166283444); \path (0.8682408883346521, 4.92403876506104) -- node [pos = 0.15,scale=.7] {$10$} node [pos = 0.85,scale=.7] {$10$} (-4.698463103929543, -1.7101007166283433); \path (0.8682408883346521, 4.92403876506104) -- node [pos = 0.15,scale=.7] {$11$} node [pos = 0.85,scale=.7] {$11$} (-2.500000000000002, -4.330127018922192); \path (0.8682408883346521, 4.92403876506104) -- node [pos = 0.15,scale=.7] {$3$} node [pos = 0.85,scale=.7] {$3$} (0.8682408883346499, -4.924038765061041); \path (0.8682408883346521, 4.92403876506104) -- node [pos = 0.15,scale=.7] {$2$} node [pos = 0.85,scale=.7] {$2$} (3.830222215594889, -3.213938048432698); \path (-2.499999999999999, 4.330127018922194) -- node [pos = 0.15,scale=.7] {$0$} node [pos = 0.85,scale=.7] {$0$} (-4.698463103929542, 1.7101007166283444); \path (-2.499999999999999, 4.330127018922194) -- node [pos = 0.15,scale=.7] {$1$} node [pos = 0.85,scale=.7] {$1$} (-4.698463103929543, -1.7101007166283433); \path (-2.499999999999999, 4.330127018922194) -- node [pos = 0.15,scale=.7] {$4$} node [pos = 0.85,scale=.7] {$4$} (-2.500000000000002, -4.330127018922192); \path (-2.499999999999999, 4.330127018922194) -- node [pos = 0.15,scale=.7] {$5$} node [pos = 0.85,scale=.7] {$5$} (0.8682408883346499, -4.924038765061041); \path (-2.499999999999999, 4.330127018922194) -- node [pos = 0.15,scale=.7] {$10$} node [pos = 0.85,scale=.7] {$10$} (3.830222215594889, -3.213938048432698); \path (-4.698463103929542, 1.7101007166283444) -- node [pos = 0.15,scale=.7] {$6$} node [pos = 0.85,scale=.7] {$6$} (-4.698463103929543, -1.7101007166283433); \path (-4.698463103929542, 1.7101007166283444) -- node [pos = 0.15,scale=.7] {$9$} node [pos = 0.85,scale=.7] {$9$} (-2.500000000000002, -4.330127018922192); \path (-4.698463103929542, 1.7101007166283444) -- node [pos = 0.15,scale=.7] {$8$} node [pos = 0.85,scale=.7] {$8$} (0.8682408883346499, -4.924038765061041); \path (-4.698463103929542, 1.7101007166283444) -- node [pos = 0.15,scale=.7] {$3$} node [pos = 0.85,scale=.7] {$3$} (3.830222215594889, -3.213938048432698); \path (-4.698463103929543, -1.7101007166283433) -- node [pos = 0.15,scale=.7] {$8$} node [pos = 0.85,scale=.7] {$8$} (-2.500000000000002, -4.330127018922192); \path (-4.698463103929543, -1.7101007166283433) -- node [pos = 0.15,scale=.7] {$4$} node [pos = 0.85,scale=.7] {$4$} (0.8682408883346499, -4.924038765061041); \path (-4.698463103929543, -1.7101007166283433) -- node [pos = 0.15,scale=.7] {$14$} node [pos = 0.85,scale=.7] {$14$} (3.830222215594889, -3.213938048432698); \path (-2.500000000000002, -4.330127018922192) -- node [pos = 0.15,scale=.7] {$2$} node [pos = 0.85,scale=.7] {$2$} (0.8682408883346499, -4.924038765061041); \path (-2.500000000000002, -4.330127018922192) -- node [pos = 0.15,scale=.7] {$6$} node [pos = 0.85,scale=.7] {$6$} (3.830222215594889, -3.213938048432698); \path (0.8682408883346499, -4.924038765061041) -- node [pos = 0.15,scale=.7] {$12$} node [pos = 0.85,scale=.7] {$12$} (3.830222215594889, -3.213938048432698); \draw node[scale=.8] at (0,-2) {\phantom{Hey}}; \end{tikzpicture} \end{center} \caption{A $4$-intersection edge-coloring of $K_9$ with 15 colors.} \label{fig:i4k9coloring} \end{figure} %\input{col4intk9.tex} \end{center} \section{Complete bipartite graphs}\label{sec:complete_bipartite} In this section we give an exact formula for the $k$-intersection chromatic number of complete bipartite graphs. \begin{theorem} If integers $1 \le k \le m \le n$, then $\chik k(K_{m,n}) = \lceil \frac{mn}{k} \rceil$. \end{theorem} \begin{proof} Let $\phi$ be a $k$-intersection edge-coloring of $K_{m,n}$ using colors from a set $C$ of cardinality $\chik k(K_{m,n})$. Let $A = \{0,1,\ldots, m-1\}$ and $B = \{0,1,\ldots,n-1\}$ be two parts of $K_{m,n}$. Let $a\in A$ be a vertex and let $\phi(a)=\{ c_1, c_2, \ldots, c_n\}$ be the set of colors of the edges incident to $a$. Furthermore, let $G_a$ be the subgraph induced by the edges whose color is in $\phi(a)$. From the definition of $k$-intersection edge-coloring, we deduce that for every vertex $b$ in $B$, $d_{G_a}(b) \leq k$. Therefore, $|E(G_a)|\leq km$. Given $c\in C$ let $d(c)$ be the number of edges colored $c$. It is easily seen that $\sum_{a\in A}\sum_{c\in \phi(a)}d(c)= \sum_{c\in C}d^2(c)$. That is because there are exactly $d(c)$ vertices in $A$ each with an incident edge of color $c$. But on the other hand $\sum_{c\in \phi(a)}d(c)= |E(G_a)|$. Therefore, $\sum_{c\in C}d^2(c)\leq kmn$. Since $\sum_{c\in C}d(c)=|E(K_{n,m})|=mn$, by the Cauchy-Schwarz inequality, $|C|(\frac{nm}{|C|})^2\leq kmn$ and so $\chik k(K_{m,n}) = |C| \geq \left\lceil \frac{mn}{k} \right\rceil$. It remains to show that $K_{m,n}$ admits a $k$-intersection edge-coloring using $p = \left\lceil \frac{mn}{k} \right\rceil$ colors. In general, an edge-coloring of $K_{m,n}$ is equivalent to an $m \times n$ matrix where rows are labelled by $A$ and columns are labelled by $B$. To have a proper edge-coloring the elements of each row (and column) must be distinct. For such an edge-coloring to be a $k$-intersection edge-coloring it is necessary and sufficient that for each pair of a row and a column there are at most $k$ entries in common. In order to give such a matrix we first consider a lexicographic order on the entries of the $m\times n$ matrix: the top left entry is first and then left to right, top to bottom order. Following this order, fill the entries by assigning 0 to the first one and the value of the previous entry $+1\pmod p$ to obtain the value of the next entry. This assignment is not yet a proper edge-coloring. In fact, a whole row might be repeated and this will be the case for row $\ell$ if $\ell n$ is a multiple of $p$. Thus to ensure a proper edge-coloring we update our procedure as follows. After completing $\ell n$ entries where $p$ divides $\ell n$, to obtain the next entry we add $+2\pmod p$. The precise formula is given by $$ f(i,j) = ( i n + j + \lfloor i/s \rfloor ) \mbox{\ mod \ } p \quad (i \in A, j \in B), $$ where $s =$ lcm$(p,n)/n$. We denote this matrix by $P_{mn,k}$. See Table~\ref{tab:complete_bipartite} for the example when $k=7, m=10, n=12$ (thus $p= 18, s=3$). Note that the jump happens at entries with $*$ sign, that is when we reach a multiple of $p$ and $n$ in our lexicographic order. \begin{table}[!ht] $$ \begin{array}{c||c|c|c|c|c|c|c|c|c|c|c|c||} f & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\ \hline\hline 0 & \textbf{\textcolor{cyan}{0}} & \textbf{\textcolor{cyan}{1}} & 2 & 3 & 4 & 5 & 6 & 7 & \textbf{\textcolor{blue}{8}} & \textbf{\textcolor{blue}{9}} & \textbf{\textcolor{blue}{10}} & \textbf{\textcolor{blue}{11}}\\ \hline 1 & \textbf{\textcolor{blue}{ 12}} & \textbf{\textcolor{blue}{13}} & \textbf{\textcolor{blue}{ 14}} & \textbf{\textcolor{blue}{15}} & \textbf{\textcolor{blue}{16 }} & \textbf{\textcolor{blue}{17 }} & \textbf{\textcolor{blue}{0}} & \textbf{\textcolor{blue}{1}} & 2 & 3 & 4 & 5 \\ \hline 2 & 6 & 7 & \textbf{\textcolor{cyan}{8}} & \textbf{\textcolor{cyan}{9}} & \textbf{\textcolor{cyan}{10}} & \textbf{\textcolor{cyan}{11}} & \textbf{\textcolor{cyan}{12}} & \textbf{\textcolor{cyan}{13}} & \textbf{\textcolor{cyan}{14}} & \textbf{\textcolor{cyan}{15}} & \textbf{\textcolor{cyan}{16}} & \textbf{\textcolor{cyan}{~17}}*\\ \specialrule{2pt}{0pt}{0pt} 3 & \textbf{\textcolor{blue}{1}} & 2 & 3 & 4 & 5 & 6 & 7 & \textbf{\textcolor{cyan}{8}} & \textbf{\textcolor{cyan}{9}} & \textbf{\textcolor{cyan}{10}} & \textbf{\textcolor{cyan}{11}} & \textbf{\textcolor{cyan}{12}}\\ \hline 4 & \textbf{\textcolor{cyan}{13}} & \textbf{\textcolor{cyan}{14}} & \textbf{\textcolor{cyan}{15}} & \textbf{\textcolor{cyan}{16}} & \textbf{\textcolor{cyan}{17}} & \textbf{\textcolor{cyan}{0}} & \textbf{\textcolor{cyan}{1}} & 2 & 3 & 4 & 5 & 6 \\ \hline 5 & 7 & \textbf{\textcolor{blue}{8}} & \textbf{\textcolor{blue}{9}} & \textbf{\textcolor{blue}{10}} & \textbf{\textcolor{blue}{11}} & \textbf{\textcolor{blue}{12}} & \textbf{\textcolor{blue}{13}} & \textbf{\textcolor{blue}{14}} & \textbf{\textcolor{blue}{15}} & \textbf{\textcolor{blue}{16}} & \textbf{\textcolor{blue}{17}} & \textbf{\textcolor{blue}{~0}}*\\ \specialrule{2pt}{0pt}{0pt} 6 & 2 & 3 & 4 & 5 & 6 & 7 & \textbf{\textcolor{cyan}{8}} & \textbf{\textcolor{cyan}{9}} & \textbf{\textcolor{cyan}{10}} & \textbf{\textcolor{cyan}{11}} & \textbf{\textcolor{cyan}{12}} & \textbf{\textcolor{cyan}{13}}\\ \hline 7 & \textbf{\textcolor{cyan}{14}} & \textbf{\textcolor{cyan}{15}} & \textbf{\textcolor{cyan}{16}} & \textbf{\textcolor{cyan}{17}} & \textbf{\textcolor{cyan}{0}} & \textbf{\textcolor{cyan}{1}} & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 8 & \textbf{\textcolor{blue}{8}} & \textbf{\textcolor{blue}{9}} & \textbf{\textcolor{blue}{10}} & \textbf{\textcolor{blue}{11}} & \textbf{\textcolor{blue}{12}} & \textbf{\textcolor{blue}{13}} & \textbf{\textcolor{blue}{14}} & \textbf{\textcolor{blue}{15}} & \textbf{\textcolor{blue}{16}} & \textbf{\textcolor{blue}{17}} & \textbf{\textcolor{blue}{0}} & \textbf{\textcolor{blue}{~1}}*\\ \specialrule{2pt}{0pt}{0pt} 9 & 3 & 4 & 5 & 6 & 7 & \textbf{\textcolor{cyan}{ 8}} & \textbf{\textcolor{cyan}{9}} & \textbf{\textcolor{cyan}{10}} & \textbf{\textcolor{cyan}{11}} & \textbf{\textcolor{cyan}{12}} & \textbf{\textcolor{cyan}{13}} & \textbf{\textcolor{cyan}{14}}\\ \hline\hline % r_m & \textbf{\textcolor{mylightblue}{15}} & % \textbf{\textcolor{mylightblue}{16}} & \textbf{\textcolor{mylightblue}{17}} & % \textbf{\textcolor{mylightblue}{0}} & \textbf{\textcolor{mylightblue}{1}} & % \textbf{\textcolor{gray}{ 2}}& & & & & & % \end{array} $$ \caption{A 7-intersection edge-coloring of $K_{10,12}$. The intersections of columns with row 8 is shown in color.} \label{tab:complete_bipartite} \end{table} We will show that $f$ is a proper edge-coloring by using the fact that $m \leq n \le p$. Indeed, in each row the colors appear consecutively$\mod p$ and since $p\geq n$, clearly all colors in a row are distinct. If $i,i' \in A$ and $j \in B$ are such that $f(i,j)=f(i',j)$, then $ i n + \lfloor i/s \rfloor \equiv i' n + \lfloor i'/s \rfloor$ (mod $p$) and so $ \lfloor i/s \rfloor \equiv \lfloor i'/s \rfloor$ (mod $\gcd(p,n)$). Since $k \le m \le n$, we have $p \ge m$ and so $s \ge \frac{m}{\gcd(p,n)}$ implying $\lfloor i/s \rfloor < m/s \le \gcd(p,n)$. Similarly, $\lfloor i'/s \rfloor < \gcd(p,n)$. Therefore, $\lfloor i/s \rfloor =\lfloor i'/s \rfloor$. Thus, $i n \equiv i' n $ (mod $p$) and so $i \equiv i' $ (mod $s$). This together with $\lfloor i/s \rfloor =\lfloor i'/s \rfloor$ gives $i=i'$. It remains to show that this coloring is also a $k$-intersection coloring. Let $r_i$ be an arbitrary but fixed row with $r_i=(a, a+1, \ldots, a+n-1)$ for some $a$ (all additions are modulo $p$). We prove that each column intersects $r_i$ in at most $k$ elements. This would complete our proof as $r_i$ is chosen arbitrarily. We note that each of the colors, and in particular the entries of $r_i$, appears at most $k$ times and at least $k-1$ times in the matrix. Consider the set of entries of $P_{mn,k}$ whose values belong to $r_i$. Our aim is to partition this set into $k$ \emph{segments} $P^{r_i}_1, P^{r_i}_2, \ldots, P^{r_i}_k$ such that each $P^{r_i}_j$ crosses at most one entry from a given column. Before defining the segments $P^{r_i}_j$, let us partition $P_{mn,k}$ into $\lceil\frac m s\rceil$ {\em blocks} of $s$ consecutive rows (i.e. {\em full} blocks), and possibly a last block of $< s$ rows (i.e. {\em partial} block). They appear on Table~\ref{tab:complete_bipartite} as the sets of values located between two consecutive bold horizontal lines. We note that when read in the lexicographic order, each block is a sequence of consecutive values modulo $p$, and that the value of the first entry of a full block is equal to the value of its last entry incremented by one. From the $j$-th occurrence of $a$ (in the lexicographic order) and the following $n-1$ entries we build a segment $P^{r_i}_j$. If this occurrence of $a$ is contained in a full block, and if before completing $P^{r_i}_j$ we have arrived at the last entry of this block, then we continue with the first entry of the same block. As a result, each segment is always contained in a specific block. Therefore, if all blocks are full then the coloring is indeed $k$-intersecting, as there are at most $k$ occurrences of $a$ in the matrix and each of the $k$ segments crosses a given column exactly once. Otherwise suppose the last block is a partial block, which implies that $mn$ is not divisible by $k$. We add to our matrix a partial row $r_m$ of $\epsilon$ entries such that $\frac {mn+\epsilon}k=p$, and fill them with the same pattern. Note that $\epsilon < k \leq n$. Again, the value of the first entry of this block is equal to the value of its last entry of $r_m$ incremented by one (modulo $p$). We can now use the same definition of segments as previously to define the $P^{r_i}_j$ contained in this last block. Consequently, in the extended matrix there are exactly $k$ segments $P^{r_i}_1,P^{r_i}_2,\ldots,P^{r_i}_k$ each of length $n$. By the previous argument all segments which do not contain entries from row $r_m$ cross any given column precisely once. Now, suppose that a segment covering some entries of $r_m$ crosses a given column more than once: since this segment is of length $n$ it actually crosses the column exactly twice. Hence in the initial matrix $P_{mn,k}$ this column crosses this segment only once, and the coloring is indeed $k$-intersecting. \end{proof} \section{Complexity} \label{sec:complexity} In this section we consider the complexity of the problem of determining if a given graph $G$ admits a $k$-intersection edge-coloring. Our main result is the following. \begin{theorem}\label{kciISNPComplete} Determining $\kci$ for each $1\le k\le \Delta$ is NP-complete. \end{theorem} It is known that computing $\chik{k}$ is NP-complete for $k=1$~\cite{m2002} and $k=\Delta(G)$~\cite{H1981}. \medskip \noindent The $k$-INTERSECTION $\ell$-EDGE-COLORING problem is defined as follows: INSTANCE: A graph $G$. QUESTION: Does $G$ have a $k$-intersection edge-coloring with $\ell$ colors? \bigskip \noindent The 3-COLORING problem on graphs of maximum degree 4 is NP-Complete~\cite{GJS74}, and is defined as follows: INSTANCE: A graph $G$ of maximum degree 4 QUESTION: Does $G$ have a proper vertex-coloring with three colors? \medskip In order to prove Theorem~\ref{kciISNPComplete} we use gadgets to reduce 3-COLORING of graphs with maximum degree 4 to $k$-INTERSECTION $(k+2)$-EDGE-COLORING. The gadgets are given in Figures \ref{fig:Gadget} and \ref{fig:gadget_P'}. The sub-gadget $P$ of Figure~\ref{fig:Gadget} is used to build all other gadgets. It is obtained from $K_{k, k+1}$ by adding a pendant edge at every vertex of degree $k$. We also use the labelling of vertices as given in the figure. \begin{figure}[!ht] \centering \begin{tikzpicture}[join=bevel,inner sep=0.5mm,rotate=90,xscale=.8] \foreach \x in {0,2,6} \foreach \y in {1,3,5} \draw (3,\y) -- (0,\x); \foreach \x [count=\xi] in {0,2,6} { \node (\xi) at (0,\x) [draw, circle, fill=black] {}; \node at (-2,\x) [draw, circle, fill=black] {}; \draw[-] (\xi) -- (-2,\x); } \node at (-0.3,0.3) {$x_1$}; \node at (-2.3,0.3) {$z_1$}; \node at (-0.3,2.3) {$x_2$}; \node at (-2.3,2.3) {$z_2$}; \node at (0,6.6) {$x_{k+1}$}; \node at (-2,6.6) {$z_{k+1}$}; \foreach \x [count=\yi] in {1,3,5} \node at (3,\x) [draw, circle, fill=black] {}; \node at (3.4,1) {$y_1$}; \node at (3.4,3) {$y_2$}; \node at (3.4,5) {$y_k$}; \node at (0,4) {$\ldots$}; \node at (3,4) {$\ldots$}; \end{tikzpicture} \caption{The sub-gadget $P$} \label{fig:Gadget} \end{figure} \begin{lemma} \label{lem:gadget} The graph $P$ of Figure~\ref{fig:Gadget} admits a $k$-intersection $(k+2)$-edge-coloring. Furthermore, in any such edge-coloring the set of pendant edges receive the same color. \end{lemma} \begin{proof} A $k$-intersection $(k+2)$-edge-coloring is easily obtained from a proper $(k+1)$-edge-coloring of $K_{k,k+1}$ and by assigning a same color to all the pendant edges. To prove the second part of the statement assume $\phi$ is a $k$-intersection $(k+2)$-edge-coloring of $P$ and suppose colors $1,2, \ldots, k+1$ are used at the edges incident to $x_{k+1}$. Observe that in order to have a valid $k$-intersection edge-coloring, each $y_i$ must be incident to an edge-colored with a color distinct from those used for the edges incident to $x_{k+1}$, i.e. color $k+2$. Thus color $k+2$ induces a matching of $y_i$, $1\leq i \leq k$ to $x_j$, $1\leq j\leq k$. In particular this implies that the color that is missing at $x_{k+1}$ is incident to every other $x_i$. Since the choice of $x_{k+1}$ was arbitrary, $\phi$ induces a set of $k+1$ matchings each of size $k$ between $x_i$ and $y_i$, i.e., $\phi$ induces a proper $(k+1)$-edge-coloring of $K_{k, k+1}$. In this coloring all $k+1$ colors appear on edges incident to each $y_i$, thus, to have a $k$-intersecting edge-coloring, all pendant edges must receive a same color. \end{proof} Note that the forced structure of a $k$-intersection $(k+2)$-edge-coloring proved in the previous lemma implies in particular that $P$ does not admit a $k$-intersection $(k+1)$-edge-coloring. \begin{lemma} For every $r$, there exists a $k$-intersection $(k+2)$-edge-colorable graph (see Figure~\ref{fig:gadget_P'}) with at least $r$ pendant edges such that in every $k$-intersection $(k+2)$-edge-coloring of this graph all pendant edges receive the same color. \label{pprimelemma} \end{lemma} \begin{proof} For $r\leq k+1$ such a construction is given in Lemma~\ref{lem:gadget}. Let $r>k+1$ and let $i=\lceil\frac r k\rceil$. We take $i$ copies $P_1, \dots, P_i$ of the gadget $P$ of Figure~\ref{fig:Gadget}. Let $x^j_1 z^j_1, x^j_{k+1} z^j_{k+1}$ be copies of $x_1z_1$ and $x_{k+1}z_{k+1}$ in $P_j$. Let $P'$ be obtained from $P_1,\dots,P_i$ by identifying $x^j_{k+1}$ with $z_1^{j+1}$ and $z^j_{k+1}$ with $x^{j+1}_1$ (see Figure~\ref{fig:gadget_P'}). To give a $k$-intersection $(k+2)$-edge-coloring of $P'$ we properly color the edges of each copy of $K_{k,k+1}$ in $P_j$ such that the set of colors of the edges incident to $x^{j-1}_{k+1}$ and $x_1^j$ are distinct (and so intersect on at most $k$ colors). It then follows from the previous lemma that all pendant edges must receive the same color in any such coloring. \end{proof} \begin{figure}[!ht] \centering \begin{tikzpicture}[join=bevel,inner sep=0.5mm,rotate=90] \foreach \i in {-9,-4.5,0} { \foreach \x in {1,2.5,4} \foreach \y in {1.75,3.25} \draw (1.5,\y+\i) -- (0,\x+\i); \node at (1.5,1.75+\i) [draw, circle, fill=black] {}; \node at (1.5,2.5+\i) {\ldots}; \node at (1.5,3.25+\i) [draw, circle, fill=black] {}; \foreach \x in {1,2.5,4} { \node at (0,\x+\i) [draw, circle, fill=black] {}; } \node at (-1,2.5+\i) [draw, circle, fill=black] {}; \draw[-] (0,2.5+\i) -- (-1,2.5+\i); } \node at (1.8,3.25) {$y^1_1$}; \node at (1.8,1.75) {$y^1_k$}; \node at (1.8,-1.25) {$y^2_1$}; \node at (1.8,-2.75) {$y^2_k$}; \node at (1.8,-1.25-4.5) {$y^{i}_1$}; \node at (1.8,-2.75-4.5) {$y^{i}_k$}; \draw[-] (0,1) -- (0,0.6) (0,-0.1) -- (0,-0.5); \draw[-] (0,0.6) -- (0,-0.1); \draw[-] (0,4) -- (-1,4); \node at (-1,4) [draw, circle, fill=black] {}; \node at (-1.3,4) {$z^1_1$}; \node at (-1.3,2.5) {$z^1_2$}; \node at (0,-1.25) {\ldots}; \node at (0,1.75) {\ldots}; \node at (-1.3,-2) {$z^2_{k}$}; \node at (0,-4.25) {\ldots}; \node at (0,-5.75) {\ldots}; \node at (0,-5) [draw, circle, fill=black] {}; \node at (-1.3,-6.5) {$z_k^i$}; \draw[-] (0,-8) -- (-1,-8); \node at (-1,-8) [draw, circle, fill=black] {}; \node at (-1.3,-8) {$z_{k+1}^i$}; \end{tikzpicture} \caption{Gadget $P'$ built in the proof of Lemma~\ref{pprimelemma}} \label{fig:gadget_P'} \end{figure} \begin{lemma} \label{pprimeprimelemma} Given integers $n$ and $k$, there exists a graph $M$ containing a subset $A=\{t_1,\ldots,t_n\}$ of $n$ vertices, each of degree $k-1$, such that $M$ is $k$-intersection $(k+2)$-edge-colorable, and in every such coloring and for any two vertices $x,y\in A$ the set of colors on the edges incident to $x$ is the same as the set of colors on the edges incident to $y$. \end{lemma} \begin{proof} Let $P'$ be a graph with at least $n$ pendant edges constructed in Lemma~\ref{pprimelemma}. The graph $M$ is constructed from $k-1$ distinct copies $P'_1,\dots,P'_{k-1}$ of $P'$ as follows. Let $t^i_1,\dots,t^i_n$ be $n$ vertices of degree 1 of $P'_i$. We then identify all $t^1_j,\dots,t^{k-1}_j$ for each $j$ and name $t_j$ each of the new vertices. It is easily verified that $M$ is $k$-intersection $(k+2)$-edge-colorable and that the set of colors on edges incident to $t_j$ is the same for every~$j$. \end{proof} Now we are ready to prove Theorem~\ref{kciISNPComplete}. \begin{proof} Recall that we reduce 3-COLORING of graphs of maximum degree 4 to $k$-INTER\-SECTION $(k+2)$-EDGE-COLORING. We are given the graph $G$ of an instance of 3-COLORING with maximum degree 4 on $n$ vertices. Let $P'$ be a graph constructed from Lemma~\ref{pprimelemma} with (at least) 5 pendant vertices $Z=\{z_1,\dots,z_5\}$, and let $M$ be the graph constructed from Lemma~\ref{pprimeprimelemma} with $n$ vertices $t_1,\dots,t_n$ of degree $k-1$ each. We create a new graph $F(G)$ containing $n$ copies $P'_1,\dots,P'_n$ of $P'$ and a copy of $M$. We modify now our graph by identifying together a vertex of degree 1 from a copy of $Z$ in $P'_i$ with a vertex of degree 1 from a copy of $Z$ in $P'_j$ for any edge $v_iv_j$ of $G$. At the end of this procedure, the copy of $Z$ in $P'_i$ has at least one remaining vertex of degree 1, we identify one such a vertex with $t_i$. For a fixed $k$ the number of vertices in this construction is linear in the order of $G$ and hence $F(G)$ is built in polynomial time. We claim that $G$ is 3-vertex-colorable if and only if $F(G)$ is $k$-intersection $(k+2)$-edge-colorable. First, suppose $G$ is 3-vertex-colored, and let $\phi$ be such a coloring with colors $1,2,3$. A $k$-intersection $(k+2)$-edge-coloring is obtained as follows. First, color $M$ in $F(G)$ such that each $t_i$ is incident with colors from $4,\dots,k+2$. Colour each $P'_i$ so that all pendant edges are colored with $\phi(v_i)$. We obtain a $k$-intersection $(k+2)$-edge-coloring. For the converse, suppose that $\psi$ is a $k$-intersection $(k+2)$-edge-coloring of $F(G)$. Then by Lemma~\ref{pprimeprimelemma} the sets of colors used on edges incident to $t_i$ and $t_j$ in the subgraph $M$ are the same. Let $\{4,\dots,k+2\}$ be this set. Recall that by Lemma~\ref{pprimelemma} all the pendant edges of $P'_i$ must be colored with the same colour. Let $c_i$ be this colour. Note that $c_i\notin\{4,\dots,k+2\}$ hence $c_i\in\{1,2,3\}$. Furthermore, if $v_i$ is adjacent to $v_j$ (in $G$) then $c_i\neq c_j$. Thus the assignment of colour $c_i$ to vertex $v_i$ yields a 3-vertex-coloring of $G$. \end{proof} Since the gadget we used is bipartite, our proof in fact implies that, for a fixed $k\geq 2$, finding the $k$-intersection chromatic index of bipartite graphs is an NP-complete problem. On the other hand, being equivalent to proper edge-coloring, $\Delta$-intersection edge-coloring of a bipartite graph is always possible. It would be interesting to find out where the threshold lies. \subsection*{Acknowledgements} The computations of $k$-intersection edge-colorings given in Figures~[\ref{fig:k9coloring},\ref{fig:i4k9coloring}] have been computed with both ILOG CPLEX \cite{cplex} and Sage \cite{sage}. The fourth author would like to thank the laboratory LRI of the University Paris-Sud and Digiteo foundation for their generous hospitality. He was able to carry out part of this research during his visit there. Also, the fourth author's research is supported by the Japan Society for the Promotion of Science Grant-in-Aid for Young Scientists (B) (20740095). %\bibliography{bib} \begin{thebibliography}{10} \bibitem{cplex} {IBM ILOG CPLEX} v12.5. \bibitem{andersen1992} L.D. Andersen. \newblock The strong chromatic index of a cubic graph is at most 10. \newblock {\em Discrete Mathematics}, 108(1):231--252, 1992. \bibitem{EGT} B.~Bollob{\'a}s. \newblock {\em Extremal Graph Theory}. \newblock Dover Publications, Incorporated, 2004. \bibitem{CN12} Gerard~Jennhwa Chang and N.~Narayanan. \newblock Strong chromatic index of 2-degenerate graphs. \newblock {\em Journal of Graph Theory}, 73(2):119--126, 2013. \bibitem{CS2010} M.~Chladn{\'y} and M.~Skoviera. \newblock Factorisation of snarks. \newblock {\em Electronic Journal of Combinatorics}, 17(1), 2010. \bibitem{2k2free} F.R.K. Chung, A.~Gy{\'a}rf{\'a}s, Z.~Tuza, and W.T. Trotter. \newblock The maximum number of edges in $2{K}_2$-free graphs of bounded degree. \newblock {\em Discrete Mathematics}, 81(2):129--135, 1990. \bibitem{CD} C.J. Colbourn and J.H. Dinitz. \newblock {\em Handbook of combinatorial designs}, volume~42. \newblock Chapman and Hall/CRC, 2010. \bibitem{C69} K.~Corr{\'a}di. \newblock Problem at {S}chweitzer competition. \newblock {\em Mat. Lapok}, 20:159--162, 1969. \bibitem{e88} P.~Erd\H{o}s. \newblock Problems and results in combinatorial analysis and graph theory. \newblock {\em Discrete Mathematics}, 72(1-3):81--92, 1988. \bibitem{en89} P.~Erd\H{o}s and J.~Ne\v{s}et\v{r}il [Problem]. \newblock Irregularities of partitions ({G}. {H}al{\'a}sz, {V}. {T}. {S}{\'o}s, {E}ds.). \newblock pages 162--163, 1989. \bibitem{FJ83} J.L. Fouquet and J.L. Jolivet. \newblock Strong edge-coloring of graphs and applications to multi-$k$-gons. \newblock {\em Ars Combinatoria}, 16A:141--150, 1983. \bibitem{GJS74} M.R. Garey, D.S. Johnson, and L.~Stockmeyer. \newblock Some simplified {NP}-complete graph problems. \newblock {\em Theoretical Computer Science}, 1(3):237--267, 1976. \bibitem{H1981} I.~Holyer. \newblock The {NP}-completeness of edge-coloring. \newblock {\em SIAM Journal on Computing}, 10(4):718--720, 1981. \bibitem{horak1993} P.~Hor{\'a}k, H.~Qing, and W.T. Trotter. \newblock Induced matchings in cubic graphs. \newblock {\em Journal of Graph Theory}, 17(2):151--160, 1993. \bibitem{jukna} S.~Jukna. \newblock {\em Extremal combinatorics}. \newblock Springerverlag Berlin Heidelberg, 2011. \bibitem{M72} W.~Mader. \newblock Ecken vom gradn in minimalenn-fach zusammenhängenden graphen. \newblock {\em Archiv der Mathematik}, 23(1):219--224, 1972. \bibitem{m2002} M.~Mahdian. \newblock On the computational complexity of strong edge coloring. \newblock {\em Discrete Applied Mathematics}, 118(3):239--248, 2002. \bibitem{MNS09} R.~Muthu, N.~Narayanan, and C.~R. Subramanian. \newblock On {\it k}-intersection edge colourings. \newblock {\em Discussiones Mathematicae Graph Theory}, 29(2):411--418, 2009. \bibitem{sage} W.A. Stein et~al. \newblock {\em {S}age {M}athematics {S}oftware ({V}ersion 5.10.rc1)}. \newblock The Sage Development Team, 2013. \newblock {\tt http://www.sagemath.org}. \bibitem{thesepetru} P.~Valicov. \newblock {\em On packing, colouring and identification problems}. \newblock PhD thesis, Universit{\'e} Bordeaux I, 2012. \bibitem{W75} R.M. Wilson. \newblock An existence theory for pairwise balanced designs, {III}: Proof of the existence conjectures. \newblock {\em Journal of Combinatorial Theory, Series A}, 18(1):71--79, 1975. \end{thebibliography} \end{document}