Name
Abstract | ||
|---|---|---|
A strong edge colouring of a graph G is a proper edge colouring such that every path of length 3 uses three colours. In this paper, we give some upper bounds for the minimum number of colours in a strong edge colouring of subcubic graphs as a function of the maximum average degree. We also prove the NP-completeness of the strong edge k-colouring problem for some restricted classes of subcubic planar graphs when k=4,5,6. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.endm.2011.09.075 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
strong edge colouring,subcubic graphs,maximum average degree,NP-completeness | Discrete mathematics,Graph,Combinatorics,Mathematics,Planar graph | Journal |
Volume | ISSN | Citations |
38 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hervé Hocquard | 1 | 64 | 9.38 |
| Pascal Ochem | 2 | 258 | 36.91 |
| Petru Valicov | 3 | 75 | 9.19 |