Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Graphs with twocoloured vertices
Posted:
Aug 19, 2011 5:30 AM


I am interested in the number of all graphs whose vertices are coloured in two colours (I would like to know the number of all improper colourings, not the number of bicoloured graphs, see below).
The problem can be solved in special cases (provided that the automorphism group is known) by applying Polya's theorem. Also, the number of bicoloured graphs (where vertices of the same colour must not be adjacent) is known (Harary, 1958).
I am particularly interested in connected graphs, but I would also be very happy about anything on trees.
Thanks a lot! Ivo



