Counting two-colored graphs with labeled vertices I need to count two-colored graphs with $n$ labeled vertices. Two same graphs that are differently colored are considered different, and two same graphs with different placement of the vertices are also considered different.
I have considered to apply Polya enumeration theorem, but I have failed at defining the permutation group $G$. I have also found this paper where this task is solved for unlabeled graphs, but I'm not sure how to adapt it for labeled graphs.
Edit: 2-coloring means no two connected vertices share the same color.
 A: If you want proper colorings, a good approach is to count the number of graphs for small numbers of vertices, then appeal to the OEIS.
If you don't require the graphs to be connected:
There are two on one vertex (white or black).
There are six on two vertices (with an edge, vertex 1 is white and 2 is black; or vice versa; or with no edge, $2^2$ ways.)
There are 26 on three vertices (if connected, there are two of one color and one of the other; three choices for the single vertex¸ two choices for its color (6 total). If there's only a single edge, there are three choices for its vertices, two choices for endpoint colors, and two choices for the isolated vertex's color (12 total). If there are no edges, there are $2^3$ ways.)
This leads us to http://oeis.org/A047863: "Number of labeled graphs with 2-colored nodes where black nodes are only connected to white nodes and vice versa.", which begins 1, 2, 6, 26, 162, 1442, 18306, 330626...
A formula is given there:
$$\sum_{k=0}^n \binom{n}{k}2^{k(n-k)}.$$
In retrospect, this is the number of ways to choose $k$ white vertices for each $k$, then choose whether or not to enable each of the $k(n-k)$ potential edges between white and black vertices.
