Three algorithms for graph locally harmonious colouring

Abstract

Locally harmonious colouring is a relaxed version of standard harmonious colouring which only needs that the colour pairs for adjacent edges are different. In this work, we introduce three algorithms for locally harmonious colouring of graph. The first algorithm is obtained in terms of colour exchange strategy and several procedures for graph operations are defined. The second locally harmonious colouring is designed by means of branching techniques which are based on rule design and linear programming tricks. The third algorithm we present is related to the second one which is heavily relied on the pricing optimization in which we defined the appropriate special independent set and initialization policy. It is a kind of robust colouring problem and the optimizer minimum the total weight.

Keywords:

• Harmonious colouring
• locally harmonious colouring
• special independent set

AMS Subject Classification:

• 05C70

Acknowledgements

The authors thank the reviewers for their constructive comments on improving the quality of this paper.

Notes

No potential conflict of interest was reported by the author.

Additional information

Funding

This work was partially supported by NSFC [grant number 11401519], [grant number 11371328], [grant number 11471293].