# Counting graphs on n vertices by chromatic number

are there any results on the number of graphs on n vertices that has chromatic number=k ?

I mean how many graphs on n vertices has x(G)=2,x(G)=3,......,x(G)=n-1 ?

update: infact equivalently, is there a way to count unique k-partite graphs? after that to get x(G)=k, just subtract #k-partite-#(k-1)-partite. I've been almost able to count number with x(G)=2 using a much easier way but the problem remains for k>=3

This is an expression I got for k=2 but needs to be verified: $|\chi(G)=2|=n^{n-2}\frac{n+1}{2}=\frac{n^{n-1}+n^{n-2}}{2}$

• It seems that one should be able to count this for a given number N of vertices. compute a partition into different colors, and then compute how many ways edges can be formed between these partitions. The computation may be a bit messy, but seems doable. There may be some elegant way of getting it, of course, that I am not aware of. Sep 12, 2012 at 18:16
• @arnab: you are going to run into lots of double counting due to "random" isomorphisms between graphs, if I understand the original question correctly. Sep 12, 2012 at 19:02
• @alexander: absolutely. implicit in this process will be somehow quotienting with the isomorphic sets - because for every graph, you can get the size of its isomorphic class - but that's where it will get messy I think. Sep 12, 2012 at 20:16
• So one might ask: Take a random $k$-partite graph on $n$ vertices for $n$ large. What is the asymptotic probability that the $k$-coloring provided by the $k$-partition is the only $k$-coloring up to permutation? If this isn't small then you have problems. Sep 12, 2012 at 21:35
• For the asymptotic answer, check out this paper dcs.gla.ac.uk/~pat/jchoco/clique/papersClique/bollobas.pdf by Bollobás. Sep 12, 2012 at 21:38

The formula for chromatic number 2 can't quite be right, as it gives $3/2$ when $n=2$. Number of 2-colored labeled graphs on $n$ nodes is tabulated at the Online Encyclopedia of Integer Sequences. The listing there agrees with the formula here for $n=3$ and $n=4$ but gives 360, not 375, for $n=5$. The page also references