The neighbour sum distinguishing relaxed edge colouring
作者：
Highlights：
• We introduce a neighbour sum distinguishing d-relaxed edge colouring which generalizes two well-known versions of edge colouring. Our aim is to propose a general framework for those colourings, in the spirit of the 1-2-3 Conjecture (which is on improper edge colourings) and its counterpart for proper edge colourings.
• We prove that every connected subcubic graph with at least three vertices has a neighbour sum distinguishing 2-relaxed edge colouring using 4 colours, while it is known that such graphs have a neighbour sum distinguishing proper edge colouring using 6 colours, and it is an open problem whether such graphs have a neighbour sum distinguishing proper edge colouring with 5 colours (the neighbour sum distinguishing proper edge colouring corresponds to the neighbour sum distinguishing 1-relaxed edge colouring).
• We determine an upper bound on the minimum number of colours needed for the neighbour sum distinguishing d-relaxed edge colouring of complete graphs with at least three vertices.
• We determine the minimum number of colours needed for the neighbour sum distinguishing d-relaxed edge colouring of trees with at least three vertices.
摘要
•We introduce a neighbour sum distinguishing d-relaxed edge colouring which generalizes two well-known versions of edge colouring. Our aim is to propose a general framework for those colourings, in the spirit of the 1-2-3 Conjecture (which is on improper edge colourings) and its counterpart for proper edge colourings.•We prove that every connected subcubic graph with at least three vertices has a neighbour sum distinguishing 2-relaxed edge colouring using 4 colours, while it is known that such graphs have a neighbour sum distinguishing proper edge colouring using 6 colours, and it is an open problem whether such graphs have a neighbour sum distinguishing proper edge colouring with 5 colours (the neighbour sum distinguishing proper edge colouring corresponds to the neighbour sum distinguishing 1-relaxed edge colouring).•We determine an upper bound on the minimum number of colours needed for the neighbour sum distinguishing d-relaxed edge colouring of complete graphs with at least three vertices.•We determine the minimum number of colours needed for the neighbour sum distinguishing d-relaxed edge colouring of trees with at least three vertices.
论文关键词：Neighbour sum distinguish edge colouring,Relaxed edge colouring,Subcubic graphs,
论文评审过程：Received 3 July 2021, Revised 6 November 2021, Accepted 8 December 2021, Available online 27 December 2021, Version of Record 27 December 2021.
论文官网地址：https://doi.org/10.1016/j.amc.2021.126864
