Home » Keyword index

partition


Combinatorics

Dividing up the unrestricted partitions ★★

Author(s): David S.; Newman

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

Posted by DavidSNewman
updated May 18th, 2010
2 comments
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
Graph Theory » Infinite Graphs

Unfriendly partitions ★★★

Author(s): Cowan; Emerson

If $ G $ is a graph, we say that a partition of $ V(G) $ 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

Posted by mdevos
updated October 22nd, 2007
add new comment
Combinatorics » Matroid Theory

Aharoni-Berger conjecture ★★★

Author(s): Aharoni; Berger

Conjecture   If $ M_1,\ldots,M_k $ are matroids on $ E $ and $ \sum_{i=1}^k rk_{M_i}(X_i) \ge \ell (k-1) $ for every partition $ \{X_1,\ldots,X_k\} $ of $ E $, then there exists $ X \subseteq E $ with $ |X| = \ell $ which is independent in every $ M_i $.

Keywords: independent set; matroid; partition

Posted by mdevos
updated June 11th, 2007
add new comment
Graph Theory » Topological G.T. » Coloring

Bounded colorings for planar graphs ★★

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

Question   Does there exists a fixed function $ f : {\mathbb N} \rightarrow {\mathbb N} $ so that every planar graph of maximum degree $ d $ has a partition of its vertex set into at most three sets $ \{V_1,V_2,V_3\} $ so that for $ i=1,2,3 $, every component of the graph induced by $ V_i $ has size at most $ f(d) $?

Keywords: coloring; partition; planar graph

Posted by mdevos
updated May 23rd, 2007
add new comment
Graph Theory » Coloring

Linial-Berge path partition duality ★★★

Author(s): Berge; Linial

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

Keywords: coloring; directed path; partition

Posted by berger
updated September 19th, 2007
2 comments
Syndicate content