There is a small but well-known open problem in graph coloring called the Total Coloring Conjecture. I worked on this problem several years ago and am interested in returning to it, potentially.
For a finite graph $G$ with no multi-edges, I assume it is known what a proper coloring of its vertices is. In the total coloring conjecture we also want to color the edges, i.e. assign a color to each edge such that no two edges sharing a common vertex are the same color. A total coloring is a simultaneous proper coloring of the edges and the vertices so that, as well, no edge has the same color as one of its vertices.
Let $\Delta(G)$ be the maximum valence of vertices of $G$. The total coloring conjecture, by Vizing, states that for a graph $G$ the total coloring number, i.e. the minimal number of colors needed to totally color the graph, is at most $\Delta(G) + 2$.
The method I was using was to supply total colorings of regular graphs and then embed $G$ into one. There is a bit of difference between the even and odd cases concerning this, though it didn't cause problems in practice. Given a homogeneous regular graph I was able to totally color a large number of these manually, even for high degrees, since the adjacency matrices are sort of 'modular' looking and thus susceptible to elementary arguments (putting colors of vertices on diagonals and colors of edges elsewhere).
So I am wondering, is there a nice, well-behaved family of (preferably homogeneous) regular graphs for valence $n$ that contain all regular graphs of valence $n$? What I am picturing are sort of 'longer and longer wreaths' of a single graph, chosen from some finite collection based on $n$, and some rules for braiding it together. I suppose it is alright if the regular graphs are infinite.
Does the question make sense? Perhaps negative results would also be helpful, to evaluate the feasibility of this method.