Graphs with two-coloured vertices

Discussion in 'Math Research' started by Ivo Siekmann, Aug 19, 2011.

  1. Ivo Siekmann

    Ivo Siekmann Guest

    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!
    Ivo Siekmann, Aug 19, 2011
    1. Advertisements

  2. Ivo Siekmann

    IV Guest

    if you mean the graphs with two colors: Polya enumeration with two color
    variables in the weight function (= color polynomial) c (e. g.: c = x+y)
    if you mean the graphs with two colorings: Polya enumeration with two weight
    functions (= color polynomials), or with two sets of color variables in the
    weight function, or with variables with two subscripts in the weight

    in combination with

    Harary/Palmer 1973, Polya 1937 = Read/Polya 1987:
    counting the (vertex-)rooted trees
    + counting the edge-rooted trees
    + building the trees from that by Otter's theorem
    + building the simple graphs from the trees

    It would be nice if you could find some real world applications for counting
    of graphs by two or more colorings.
    IV, Sep 23, 2011
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.