The DICT Development Group

Search for:
Search type:

Database copyright information
Server information

1 definition found
 for graph colouring
From The Free On-line Dictionary of Computing (30 December 2018) :

  graph colouring
  graph coloring
      A constraint-satisfaction problem often used
     as a test case in research, which also turns out to be
     equivalent to certain real-world problems (e.g. register
     allocation).  Given a connected graph and a fixed number of
     colours, the problem is to assign a colour to each node,
     subject to the constraint that any two connected nodes cannot
     be assigned the same colour.  This is an example of an
     NP-complete problem.
     See also four colour map theorem.

Contact=webmaster@dict.org Specification=RFC 2229