| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427183 | Information Processing Letters | 2013 | 8 Pages |
•Strong edge-colouring is NP-complete for subcubic planar graphs.•Maximum induced matching problem is NP-complete for subcubic planar graphs.•Tight upper bound for the strong chromatic index of outerplanar graphs.
A strong edge-colouring of a graph G is a proper edge-colouring such that every path of three edges uses three colours. An induced matching of a graph G is a subset II of edges of G such that the graph induced by the endpoints of II is a matching. In this paper, we prove the NP-completeness of strong 4-, 5-, and 6-edge-colouring and maximum induced matching in some subclasses of subcubic triangle-free planar graphs. We also obtain a tight upper bound for the minimum number of colours in a strong edge-colouring of outerplanar graphs as a function of the maximum degree.
