Three algorithms for graph locally harmonious colouring. Issue 1 (1st February 2017)

• Record Type: Journal Article
• Authors: Gao, Wei
• Is Part Of: Journal of difference equations and applications. Volume 23:Issue 1/2(2017)
• Page Start: 8
• Page End: 20
• Publication Date: 2017-02-01
• Subjects: Harmonious colouring -- locally harmonious colouring -- special independent set; 05C70; Difference equations -- Periodicals; 515.625
• DOI: 10.1080/10236198.2015.1124101
• Languages: English
• ISSNs: 1023-6198

Abstract

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.