Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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|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)? –  J.A 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
4  
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. –  J.A Apr 2 '12 at 20:29

Your Answer

 
discard

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.