Does having vertex transitivity make the problem of calculating independence and chromatic numbers easier?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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.
answered Apr 1, 2012 at 21:53
-
$\begingroup$ 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)? $\endgroup$– TurboCommented Apr 2, 2012 at 1:07
-
$\begingroup$ My recollection is that it does not. (You could check the paper.) $\endgroup$ Commented Apr 2, 2012 at 3:19
-
4$\begingroup$ 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. $\endgroup$ Commented Apr 2, 2012 at 12:41
-
$\begingroup$ Certainly, in a particular case transitivity can make a big difference. But I was thinking of theorems running "if $G$ is vertex transitive, then..." $\endgroup$ Commented Apr 2, 2012 at 19:35
-
$\begingroup$ @BrendanMcKay Could you elaborate? I also felt it is feasible especially if the graph is self-complementary as well. $\endgroup$– TurboCommented Apr 2, 2012 at 20:29