Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am working across mathematics, physics and engineering. And I am looking for whether there exists already formally established knowledge in the field.

Given a periodic graph (actually a physical lattice or crystal structure), we want to examine some periodic coloring ( or ordered but not periodic coloring) of the graph. This coloring in physics may be considered as filling the lattice site with atoms, ions and so forth. Is there some already formally established mathematical area that deals with the this?

Further, we could construct functions from these kinds of coloring to a real number. ( in physics we associate average energy with the specific structure) and we want to minimize it by searching the periodic or ordered graph space. Is there such a branch in mathematics dealing with this also?

Furthermore, I wish to construct a program to analyze any arbitrary periodic colored graphs (that is to analyze different crystal structure. ) By analyze I mean search the coloring that would give the minimum energy. Is there existing well established knowledge for doing this?

An reduced problem would be is there some established mathematical theorems tackling the coloring of an arbitrary periodic graph, in any possible way?

Thank you very much.

share|cite|improve this question
It seems like you could use the adjacency matrix of the graph to formulate this as a linear programming problem. (Or NLP, depending on your cost function) – Xodarap Oct 25 '13 at 23:21
'Minimum vertex colouring' are the only words that pop up in my head. Although intuitively, the minimum number of colours you'd need is equal to the degree (number of edges) of the vertex with the most edges connected to it - you can perhaps formulate an algorithm that uses that as a starting point, and since you're minimising, you can priortise the usage of lower energy 'colours'. – matthras Oct 26 '13 at 10:19
Cross-posted to – Qmechanic Nov 6 '13 at 1:53
Also cross-posted at – Joel Reyes Noche Nov 9 '13 at 0:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.