Skip to main content
Source Link
LeechLattice
  • 9.5k
  • 2
  • 23
  • 57

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.

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$.

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.

Source Link
LeechLattice
  • 9.5k
  • 2
  • 23
  • 57

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$.