On approximate graph colouring and max-k-cut algorithms based on the θ-function

• Main Authors: Klerk, Etienne de., Pasechnik, Dmitrii V., Warners, J. P.
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2013
• Subjects: DRNTU::Science::Mathematics
• Online Access: https://hdl.handle.net/10356/95230; http://hdl.handle.net/10220/9275
• Institution: Nanyang Technological University

The problem of colouring a k-colourable graph is well-known to be NP-complete, for k ≥ 3. The MAX-k-CUT approach to approximate k-colouring is to assign k colours to all of the vertices in polynomial time such that the fraction of `defect edges' (with endpoints of the same colour) is provably s...