MathOverflow is a question and answer site for professional mathematicians. 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

Does having vertex transitivity make the problem of calculating independence and chromatic numbers easier?

share|cite|improve this question
up vote 11 down vote accepted

Not particularly. There is a paper by Codenotti, Gerace, Vigna "Hardness results and spectral techniques for combinatorial problems on circulant graphs" Linear Algebra Appl. 285 (1998) 123-142 which shows that computing the chromatic number of a circulant graph is NP-hard. (The pdf is available on Codenotti's web page.) Being vertex transitive guarantees that a $k$-regular graph has vertex connectivity at at least $2(k+1)/3$ and that its edge connectivity is equal to $k$. Aside from this, it is not easy to identify useful consequences of vertex transitivity.

share|cite|improve this answer
Does the result hold if we restrict to those graphs that have exactly n(n-1)/4 edges (n is 0 or 1 mod 4) which is half the maximum (half a complete graph)? – Turbo Apr 2 '12 at 1:07
My recollection is that it does not. (You could check the paper.) – Chris Godsil Apr 2 '12 at 3:19
In practice, knowing the automorphism group can help a lot, especially if the group is large, since you can remove parts of the search space equivalent to parts you have done already. In the case of very difficult problems, this can make the difference between finishing it or not. – Brendan McKay Apr 2 '12 at 12:41
Certainly, in a particular case transitivity can make a big difference. But I was thinking of theorems running "if $G$ is vertex transitive, then..." – Chris Godsil Apr 2 '12 at 19:35
@BrendanMcKay Could you elaborate? I also felt it is feasible especially if the graph is self-complementary as well. – Turbo Apr 2 '12 at 20:29

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.