Graph Theory » Basic G.T.

Friendly partitions ★★

Author(s): DeVos

A friendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.

Problem   Is it true that for every $ r $, all but finitely many $ r $-regular graphs have friendly partitions?

Keywords: edge-cut; partition; regular

Posted by mdevos
updated August 5th, 2020
1 comment
Topology

Is there an algorithm to determine if a triangulated 4-manifold is combinatorially equivalent to the 4-sphere? ★★★

Author(s): Novikov

Problem   Is there an algorithm which takes as input a triangulated 4-manifold, and determines whether or not this manifold is combinatorially equivalent to the 4-sphere?

Keywords: 4-sphere; algorithm

Posted by rybu
updated November 7th, 2009
add new comment
Topology

What is the homotopy type of the group of diffeomorphisms of the 4-sphere? ★★★★

Author(s): Smale

Problem   $ Diff(S^4) $ has the homotopy-type of a product space $ Diff(S^4) \simeq \mathbb O_5 \times Diff(D^4) $ where $ Diff(D^4) $ is the group of diffeomorphisms of the 4-ball which restrict to the identity on the boundary. Determine some (any?) homotopy or homology groups of $ Diff(D^4) $.

Keywords: 4-sphere; diffeomorphisms

Posted by rybu
updated November 7th, 2009
add new comment
Topology

Which compact boundaryless 3-manifolds embed smoothly in the 4-sphere? ★★★

Author(s): Kirby

Problem   Determine a computable set of invariants that allow one to determine, given a compact boundaryless 3-manifold, whether or not it embeds smoothly in the 4-sphere. This should include a constructive procedure to find an embedding if the manifold is embeddable.

Keywords: 3-manifold; 4-sphere; embedding

Posted by rybu
updated November 7th, 2009
add new comment