Here are some observations that may help you improve this code.

Fix the obvious errors

The Graph::set_color() routine says that it returns a Color but it doesn't return anything. The obvious fix is to simply add return color; to that function. Alternatively, change the signature to return void. The same problem exists with set_payload.

Iterate over const references where possible

In the to_gv_dot() routine, the for loops should iterate over const references instead of forcing temporary copies. In other words, change the code from this:

for (auto j : i.second) {

to this:

for (auto const &j : i.second) {

Use defaults when sensible

The Vertex operator= is essentially the same as that which would have been generated by the compiler. To reduce the chance of error, it can be simply eliminated. If you wish to make it explicit that this is being done, use this:

Vertex &operator=(Vertex& ) = default;

Also note that it is not necessary to write Vertex<PayloadT> in this context because the compiler can infer that from the context. Omitting it makes it easer for humans to read and understand and eliminates one possibility for error.

Consider adding debug-friendly methods

The Vertex class can be more easily debugged by adding a few lines of code. First this code just below the Color enum:

static const char *colorname[] = { "white", "gray", "black", "red", "none" };

Then these class members in the Vertex class:

    const char *get_color_name() const { return colorname[color]; }
    friend std::ostream &operator<<(std::ostream &out, const Vertex &v) {
        return out << "{ " << v.get_payload() << ", " << v.get_color_name() 
            << " }\n";
    }

The get_color_name() routine can also be used to enhance the existing output for dot. In the to_gv_dot() routine, the line after the first for can be this:

    stm << "\t" << i.first.get_payload() << "[style=filled,fillcolor=" 
        << i.first.get_color_name() << "];\n";

Have public methods return user-centric values

Graph has a get_size() function which seems like it ought to return the number of vertices or the number of edges, but it does neither. Instead it returns the number of unique nodes which are sources of directed edges to other nodes. It would make more sense for this function to return something such as number of nodes or number of edges which would make sense to the user of the graph.

Fix rm_vertex

The rm_vertex() method of Graph purports to remove a vertex, but in fact, it only eliminates part of the internal data structure. If one has the graph

a -> b -> c

and then calls rm_vertex(b) the resulting graph will be

a -> b

even though the user just asked to delete that vertex. That can't be right.

Consider the user when designing the interface

There is no way to simultaneously set the contents and the color when constructing a Vertex. Also, once a Vertex is created and inserted into a Graph, there's no way to get it back or refer to it.

Avoid using a leading underscore for items in global namespace

As you can read in this answer, global names that begin with an underscore are "reserved to the implementation;" that is, they are for your compiler rather than for you.

Consider providing iterators

An obvious thing to do with a graph is to iterate over edges or nodes. It would be nice for your interface to provide this.

Decide if nodes that differ only in color are actually different

Right now, if two nodes differ only in color, the operator== for the Vertex class reports that they are not equal. However, if two nodes differ only in color, they will be shown on the dot graph as only a single node.