Dividing up the unrestricted partitions ★★

Author(s): David S.; Newman

Begin with the generating function for unrestricted partitions:


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 \emph{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.

\begin{problem} Is it true that for every $r$, all but finitely many $r$-regular graphs have friendly partitions? \end{problem}

Keywords: edge-cut; partition; regular

Unfriendly partitions ★★★

Author(s): Cowan; Emerson

If $G$ is a graph, we say that a partition of $V(G)$ is \emph{unfriendly} if every vertex has at least as many neighbors in the other classes as in its own.

\begin{problem} Does every countably infinite graph have an unfriendly partition into two sets? \end{problem}

Keywords: coloring; infinite graph; partition

Aharoni-Berger conjecture ★★★

Author(s): Aharoni; Berger

\begin{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$. \end{conjecture}

Keywords: independent set; matroid; partition

Bounded colorings for planar graphs ★★

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

\begin{question} Does there exists a fixed function $f : {\mathbb N} \rightarrow {\mathbb N}$ so that every \Def[planar]{planar graph} 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)$? \end{question}

Keywords: coloring; partition; planar graph

Linial-Berge path partition duality ★★★

Author(s): Berge; Linial

\begin{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. \end{conjecture}

Keywords: coloring; directed path; partition

Syndicate content