On k-intersection edge colourings
Rahul Muthu, N. Narayanan, Charumathi Raghu Subramanian · Discussiones Mathematicae Graph Theory · 2009
We propose the following problem. For some k ≥ 1, a graph G is to be properly edge coloured such that any two adjacent vertices share at most k colours. We call this the k-intersection edge colouring. The minimum number of colours sufficient to guarantee such a colouring is the k-intersection chromatic index and is denoted χ ′ k (G). Let fk be defined by fk(∆) = max G:∆(G)= ∆ {χ ′ k (G)}. We show that fk(∆) = Θ ( ∆2