CS157 Fourth Unit Assignment: Category 2 -- Graph Coloring

A neighbor of a node is any node that is connected to it. A node is colored either blue, red, green, or yellow. No node can have the same color as its neighbor. Use the predicates node, color, neighbor, and the constants red, green, blue, yellow to formalize this situation.

The maximum depth for problems in this category is 20.

Your solution will contain the following:

1. A rewriting of the Background Axioms
2. An inference method: Logica or Epilog
3. Strategies appropriate for your chosen inference method.

Background Axioms

your set of axioms that describe the above situation

Sample Premises

(node a)
(node b)
(node c)
(node d)
(neighbor a b)
(neighbor a c)
(neighbor a d)
(neighbor b c)
(neighbor b d)
(neighbor c d)
(color blue a)
(color green b)
(color yellow c)

Sample Conclusion

(color red d)