HMM tagger - Baum Welch training
Actually, there are only $459^3$ transitions, not $459^4$ transitions.  That helps a lot.  This is because a state is a pair $(t,u)$ where $t,u$ are tags, and a transition has the form $(t,u)\to (u,v)$.  In particular, you can't have $(t,u) \to (w,x)$ where $u \ne w$ (given that the state represents the last two tags).  So, there are at most $459^3$ transitions, or at most about 100 million transitions.  You should be able to store that a graph with 100 million edges in memory without too much difficulty.

My guess would be that not all transitions actually occur in the training set, so it's possible this might be a sparse graph, and that might reduce the graph size further.