For instance, suppose I have a graph G = (V, E) where
V = {A, B, C, D}
E = {(A, B), (A,D), (C, D)}
This graph is bipartite, and thus can be split into two disjoint sets {A, C} and {B, D}. My first guess is that I can simply walk the graph and assign alternating colors to each vertex. Is this the case, or is it more complicated/simpler than this? Are there any known algorithms for this?
Your first guess is correct - traverse the graph and alternate.
The algorithm should be simple. I'd keep two queues of nodes to visit, one for each colour. Pop nodes off the queues alternately, mark its colour, and push any non-visited adjacent nodes into the queue for the opposite colour. Terminate when the number of visited nodes + the length of both queues = number of nodes in the graph.