2026/07/29 by Jitendra Prajapati
Mathematics · #math.CO #msc:05C15 #msc:05C76 #msc:05E05
4 pages. Verification code and exhaustive census data at https://github.com/infinityscroll/claw-free-schur-counterexample
arxiv created 2026/07/29 · arxiv updated 2026/07/30
The claw-free Schur-positivity conjecture, recorded by Stanley (1998) and credited there to Gasharov, asserts that the chromatic symmetric function of every claw-free graph is Schur-positive. We give a counterexample on 12 vertices: the line graph G of the graph obtained from a 4-cycle by attaching triangles at two opposite vertices and pendant edges at the other two satisfies [s(3,3,3,3)]XG = -64. The coefficient follows from a short computation by hand and is also reproduced by three exact implementations. An exhaustive computation over all 216,777 connected claw-free graphs on at most 11 vertices shows that every one is Schur-positive, so 12 vertices is the minimum order of any counterexample. A complete census of the 1,728,404 connected claw-free graphs on 12 vertices finds exactly two non-Schur-positive isomorphism classes; the other has graph6 code K?`CR@`bAbRB and coefficient [s(3,3,3,3)] = -40.