Name
Abstract | ||
|---|---|---|
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 I of edges of G such that the graph induced by the endpoints of I 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.ipl.2013.07.026 | Inf. Process. Lett. |
Keywords | Field | DocType |
maximum degree,outerplanar graph,strong edge-colouring,graph g,minimum number,maximum induced matching,induced matching,subcubic triangle-free planar graph,induced matchings,np completeness,planar graphs,computational complexity | Perfect graph,Edge coloring,Discrete mathematics,Combinatorics,Outerplanar graph,Line graph,Cograph,Pathwidth,1-planar graph,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
113 | 19-21 | 0020-0190 |
Citations | PageRank | References |
5 | 0.54 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hervé Hocquard | 1 | 64 | 9.38 |
| Pascal Ochem | 2 | 258 | 36.91 |
| Petru Valicov | 3 | 75 | 9.19 |