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

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}$

share|improve this question
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. –  Arnab Sep 12 '12 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. –  Alexander Woo Sep 12 '12 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. –  Arnab Sep 12 '12 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. –  Will Sawin Sep 12 '12 at 21:35
For the asymptotic answer, check out this paper dcs.gla.ac.uk/~pat/jchoco/clique/papersClique/bollobas.pdf by Bollobás. –  Tony Huynh Sep 12 '12 at 21:38
show 2 more comments

1 Answer 1

up vote 2 down vote accepted

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

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 18, table 1.5.1, column 2 (divided by 2) and

R. C. Read, The number of k-colored graphs on labeled nodes, Canad. J. Math., 12 (1960), 410-414.

share|improve this answer
add comment

Your Answer


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.