Graph Colouring with SAT - Maple Application Center
Application Center Applications Graph Colouring with SAT

Graph Colouring with SAT

Author
: Curtis Bright
Engineering software solutions from Maplesoft
This Application runs in Maple. Don't have Maple? No problem!
 Try Maple free for 15 days!
A colouring of a graph is an assignment of colours to its vertices such that every two adjacent vertices are coloured differently. Finding a colouring of a given graph using the fewest number of colours is a difficult problem in general. In this worksheet we demonstrate how to solve the graph colouring problem by translating it into Boolean logic and using Maple's built-in efficient SAT solver. This approach is now available as an option to Maple’s ChromaticNumber function, which also solves the graph colouring problem. Using SAT can dramatically improve the performance of this function in some cases, including the “queen graphs” problem shown in this application.

Application Details

Publish Date: September 09, 2019
Created In: Maple 2018
Language: English

More Like This

Solving the World's Hardest Sudoku
Solving the Einstein Riddle
Pascal's triangle and its relationship to the Fibonacci sequence
Solving constraint satisfaction problems II: More difficult logic problems
Finding Minimal Sum for Boolean Expression
Finding Graeco-Latin Squares
Solving constraint satisfaction problems I: Logic problems
Prime Implicants of Boolean Expression by Concensus method