






























Let $χ'_\subset(G)$ be the least number of colours necessary to properly colour the edges of a graph $G$ with minimum degree $δ\geq 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 $χ'_\subset(G)\geq (1+\frac{1}{δ-1})Δ$, where $Δ$ is the maximum degree of $G$, and we conjecture that $χ'_\subset(G)\leq \lceil(1+\frac{1}{δ-1})Δ\rceil$ for every connected graph with $δ\geq 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 $δ\ge2$, $χ'_\subset(G) \le (1+\frac{4}δ)Δ(1+o(1))$ (for $Δ\to\infty$), what implies that $χ'_\subset(G) \le (1+\frac{4}{δ-1})Δ$ for $Δ$ large enough.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。