0
votes
0answers
18 views

Partition of the node set of a graph into connected subsets

What word is most commonly used in graph theory for a partition of the node set of an undirected graph into connected subsets? More rigorously: Given an undirected graph $(V,E)$, a partition $S ...
1
vote
1answer
77 views

Number of 2n-1 equal size partitions up to symmetry

Consider the $K_{2n}$ (or just the set $\{1,\dots,2n\}$) with $S_{2n}$ acting on the vertices. Moreover consider a collection of 2n-1 partitions of the vertices into two equal sized sets (repeated ...
1
vote
1answer
23 views

Prove a graph can be partitioned into two groups where every vertex has half its edges cross?

I'm trying to show that for any graph with more than 2 vertices, the graph can be partitioned into two groups such that for every vertex at least half of the vertices its connected to are in the other ...
0
votes
1answer
28 views

Make a partition that contains a set of points??

I am given a set of $M$ points in a segment (the edges are also points in this set) I would like to partition the segment (with equidistant points), in such a way that my partition contains all these ...
0
votes
1answer
70 views

What is minimum Eulerian partition?

I have a homework in my graph course. It asks something about minimum Eulerian partition but it doesn't give any information about it. I googled it but couldn't come up anything useful and clear. Is ...
1
vote
0answers
101 views

Shifted Young tableaux & Hook numbers & Bulgarian Solitaire

I would like to find articles or documentation regarding this process: Starting from what ever integer partition, e.g. 5,2 for the number 7. Construct his Young tableaux and then fill it with Hook ...
3
votes
2answers
328 views

Graph coloring problem (possibly related to partitions)

Given an undirected graph I'd like to color each node either black or red such that at most half of every node's neighbors have the same color as the node itself. As a first step, I'd like to show ...