Linear programming formulation of the vertex colouring problem

Moustapha Diaby

International Journal of Mathematics in Operational Research, 2010, vol. 2, issue 3, 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 (δ⁹·ς³) and O (δ⁸·ς³), 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. (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.inderscience.com/link.php?id=32718 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijmore:v:2:y:2010:i:3:p:259-289

Access Statistics for this article

More articles in International Journal of Mathematics in Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().