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

Improve this question
$\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
    Commented 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$
    – Alexander Woo
    Commented 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
    Commented 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
    Commented 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
    Commented Sep 12, 2012 at 21:38

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .