Motzkin and Taussky (and independently, Gerstenhaber) proved that the unital algebra generated by a pair of commuting $d\times d$ matrices over a field has dimension at most $d$. Since then, it has remained an open problem to determine whether the analogous statement is true for triples of matrices which pairwise commute. We answer this question for combinatorially-motivated classes of such triples.