Vertex transitive graphs - MathOverflow 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 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 Answer by Chris Godsil for Vertex transitive graphs 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>