  We present a means of formulating and solving graph coloring problems with
probabilistic graphical models. In contrast to the prevalent literature that
uses factor graphs for this purpose, we instead approach it from a cluster
graph perspective. Since there seems to be a lack of algorithms to
automatically construct valid cluster graphs, we provide such an algorithm
(termed LTRIP). Our experiments indicate a significant advantage for preferring
cluster graphs over factor graphs, both in terms of accuracy as well as
computational efficiency.
