On inclusion chromatic index of a graph

Abstract

Let ${\chi }_{\subset }^{\prime }(G)$ be the least number of colours necessary to properly colour the edges of a graph $G$ with minimum degree $\delta \ge 2$ so that the set of colours incident with any vertex is not contained in a set of colours incident to any its neighbour. We provide an infinite family of examples of graphs $G$ with ${\chi }_{\subset }^{\prime }(G)\ge (1+\frac{1}{\delta -1})\Delta$, where $\Delta$ is the maximum degree of $G$, and we conjecture that ${\chi }_{\subset }^{\prime }(G)\le \lceil (1+\frac{1}{\delta -1})\Delta \rceil$ for every connected graph with $\delta \ge 2$ which is not isomorphic to $C_5$. The equality here is attained e.g. for the family of complete bipartite graphs. Using a probabilistic argument we support this conjecture by proving that for any fixed $\delta \ge 2$, ${\chi }_{\subset }^{\prime }(G)\le (1+\frac{4}{\delta })\Delta (1+o(1))$ (for $\Delta \to \infty$), what implies that ${\chi }_{\subset }^{\prime }(G)\le (1+\frac{4}{\delta -1})\Delta$ for $\Delta$ large enough.

11 pages