\(r\)-strong edge colorings of graphs (Q856841): Difference between revisions

If \(G\) is a graph and \(n\) a natural number, \(\chi(G,n)\) denotes the minimum number of colours required for a proper edge colouring of \(G\) in which no two vertices with distance at most \(n\) are incident to edges coloured with the same set of colours. The following is proved: (a) For any tree \(T\) with at least three vertices, \(\chi(T,2)\leq\Delta(T)+ 1\), where \(\Delta(T)\) is the maximum vertex degree of \(T\). (b) Let \(T\) be a tree. If \(d(u,v)\geq 3\) for any two vertices \(u\) and \(v\), then \(\chi(T,2)= \Delta(T)\). (c) For any graph \(G\) with no isolated edges, \(\chi(G,1)\leq 3\Delta(G)\).