Title: Linear programming formulation of the vertex colouring problem

 

Author: Moustapha Diaby

 

Address: Operations and Information Management, University of Connecticut, Storrs, CT 06268, USA

 

Journal: Int. J. of Mathematics in Operational Research, 2010 Vol.2, No.3, pp.259 - 289

 

Abstract: In this paper, 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 (δ9·ς3) and O (δ8·ς3), respectively, where δ and ς 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.

 

Keywords: vertex colouring; graph colouring; vertex packing; linear programming; combinatorial optimisation; computational complexity; bipartite network flow; graph-based modelling.

 

DOI: http://dx.doi.org/10.1504/IJMOR.2010.032718

 

Available online 17 Apr 2010

 

 

Editors Full Text AccessAccess for SubscribersPurchase this articleComment on this article