The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math.research

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Graphs with two-coloured vertices
Replies: 1   Last Post: Sep 23, 2011 10:30 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Ivo Siekmann

Posts: 4
Registered: 6/7/09
Graphs with two-coloured vertices
Posted: Aug 19, 2011 5:30 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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 bi-coloured 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 bi-coloured 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!

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.