Linear programming formulation of the vertex colouring problem (Q975796)

Summary: We present a first linear programming (LP) formulation of the vertex colouring problem (VCP). The complexity orders of the number of variables and the number of constraints of the proposed LP are \(O(\delta ^{9} \cdot \varsigma ^{3})\) and \(O (\delta ^{8} \varsigma ^{3})\), respectively, where \(\delta \) and \(\varsigma\) are the number of vertices and the number of available colours in the VCP instance, respectively. Hence, the proposed model represents a reaffirmation of \('P\) = NP'. First, we develop a bipartite network flow (BNF) based model of the problem. Then, we use a graph-based modelling framework similar to that of Diaby to develop the proposed LP model. A numerical example is used to illustrate the approach.