Uniform partitioning of regular graphs Consider a symmetric or arc-transitive graph except the odd cycle. Then, is it true that the graph could be partitioned into distinct parts such that each part has equal number of vertices except for a few singleton parts(which consists of single vertex) and such that each vertex in each part is adjacent to some other vertex in every other part except the part in which it is(the vertices in a part are independent) and the number of parts is $\le\Delta+1$ where $\Delta$ is the maximum degree?
I think this should be true, as any the graph is both vertex and edge transitive, hence any edge as well as vertex must be equivalent under an automorphism, thus the partitions must also be equivalent. Is the fact true for graphs that are only vertex transitive and not necessarily symmetric or edge transitive? What about Cayley graphs? or, restrictively, Cayley graphs of abelian groups? Thanks beforehand.
 A: Every connected vertex-transitive graph on an even number of vertices has a perfect matching, and each vertex in a connected vertex-transitive graph on an odd number of vertices is missed by a matching that covers all remaining vertices, see here.
So, for the even number of vertices case, choose a perfect matching $(u_1,v_1),(u_2,v_2),...$ and partition the graph into parts $u$ and $v$.
For the odd number of vertices case, remove a vertex $a$ and choose a perfect matching $(u_1,v_1),(u_2,v_2),...$ of the remaining graph and partition the graph into parts $u$, $v$ and $a$.    
EDIT: It's not possible if the classes are required to be independent: 
Consider the symmetric non-bipartite cubic graph on 182 vertices. If a partition were possible, the size of the classes must be in the following list:
91+91
1+1+180
1+1+90+90
1+1+1+179

$91+91$ is impossible by non-bipartiteness. 
$1+1+180$ and $1+1+1+179$ are impossible by bounding on the largest independent set (the size is $77$). 
$1+1+90+90$ is impossible by checking non-bipartiteness of all $2$-vertex-removed subgraphs: none of the $2$-vertex-removed subgraphs are bipartite.
So such a partition does not exist.
