# partition

## Dividing up the unrestricted partitions ★★

Begin with the generating function for unrestricted partitions:

(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...

Now change some of the plus signs to minus signs. The resulting series will have coefficients congruent, mod 2, to the coefficients of the generating series for unrestricted partitions. I conjecture that the signs may be chosen such that all the coefficients of the series are either 1, -1, or zero.

Keywords: congruence properties; partition

## 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 , all but finitely many -regular graphs have friendly partitions?

## Unfriendly partitions ★★★

If is a graph, we say that a partition of is *unfriendly* if every vertex has at least as many neighbors in the other classes as in its own.

**Problem**Does every countably infinite graph have an unfriendly partition into two sets?

Keywords: coloring; infinite graph; partition

## Aharoni-Berger conjecture ★★★

**Conjecture**If are matroids on and for every partition of , then there exists with which is independent in every .

Keywords: independent set; matroid; partition

## Bounded colorings for planar graphs ★★

Author(s): Alon; Ding; Oporowski; Vertigan

**Question**Does there exists a fixed function so that every planar graph of maximum degree has a partition of its vertex set into at most three sets so that for , every component of the graph induced by has size at most ?

Keywords: coloring; partition; planar graph

## Linial-Berge path partition duality ★★★

**Conjecture**The minimum -norm of a path partition on a directed graph is no more than the maximal size of an induced -colorable subgraph.

Keywords: coloring; directed path; partition