most recent 30 from http://mathoverflow.net 2013-05-23T17:16:58Z http://mathoverflow.net/feeds/question/92847 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/92847/vertex-transitive-graphs unknown (google) 2012-04-01T20:38:17Z 2012-04-02T19:33:38Z

<p>Does having vertex transitivity make the problem of calculating independence and chromatic numbers easier?</p>

http://mathoverflow.net/questions/92847/vertex-transitive-graphs/92850#92850 Chris Godsil 2012-04-01T21:53:28Z 2012-04-02T19:33:38Z

<p>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.</p>