4
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Arnab
    Sep 12, 2012 at 18:16
  • $\begingroup$ @arnab: you are going to run into lots of double counting due to "random" isomorphisms between graphs, if I understand the original question correctly. $\endgroup$ Sep 12, 2012 at 19:02
  • $\begingroup$ @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. $\endgroup$
    – Arnab
    Sep 12, 2012 at 20:16
  • $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Sep 12, 2012 at 21:35
  • 1
    $\begingroup$ For the asymptotic answer, check out this paper dcs.gla.ac.uk/~pat/jchoco/clique/papersClique/bollobas.pdf by Bollobás. $\endgroup$
    – Tony Huynh
    Sep 12, 2012 at 21:38

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.