Strong chromatic index of K4-minor free graphs

- We study the strong edge colouring of K4-minor-free graphs.
- We give a tight upper bound for the strong chromatic index of K4-minor-free graphs.
- A structural lemma is established.
- Some examples to attain tightness is constructed.

The strong chromatic index χs′(G) of a graph G is the smallest integer k such that G has a proper edge k-colouring with the condition that any two edges at distance at most 2 receive distinct colours. In this paper, we prove that if G is a K4-minor free graph with maximum degree Δ≥3, then χs′(G)≤3Δ−2. The result is best possible in the sense that there exist K4-minor free graphs G with maximum degree Δ such that χs′(G)=3Δ−2 for any given integer Δ≥3.