Refutation of conjecture 135 of Siemion Fajtlowicz, *Written on the Wall*

Part A -- structure of the witness M^2(C5)
  ok   the witness has 23 vertices
  ok   the witness has 71 edges
  ok   connected
  ok   triangle-free (0 triangles)
  ok   diameter = 2 (computed 2)

Part B -- clique number
  ok   omega = 2 (computed 2); it has an edge, and no triangle

Part C -- chromatic number is exactly 5
  ok   an explicit proper 5-colouring exists and is verified proper
  ok   exhaustive search proves NO proper 4-colouring exists
       5-colouring: [0, 1, 0, 1, 2, 3, 1, 2, 1, 2, 0, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 4, 0]

Part D -- the book's D2 and its independence number
  ok   |E(D2)| = 182 (computed 182)
  ok   alpha(D2) = 2 (computed 2)
  ok   no 3 vertices are pairwise at distance != 2 (triangle-free + diameter 2 forces alpha(D2) <= 2)

Part E -- conjecture 135 fails on this graph
  ok   chi/omega = 2.5 > 2 = alpha(D2):  margin -0.5

Part F -- the failure is unbounded: G_k = M^k(C5)
  ok   k=0: n=  5, m=   5, triangle-free, diameter 2, alpha(D2)=2, proper 3-colouring exhibited => chi/omega = 1.5, margin +0.5
  ok   k=1: n= 11, m=  20, triangle-free, diameter 2, alpha(D2)=2, proper 4-colouring exhibited => chi/omega = 2.0, margin +0.0
  ok   k=2: n= 23, m=  71, triangle-free, diameter 2, alpha(D2)=2, proper 5-colouring exhibited => chi/omega = 2.5, margin -0.5
  ok   k=3: n= 47, m= 236, triangle-free, diameter 2, alpha(D2)=2, proper 6-colouring exhibited => chi/omega = 3.0, margin -1.0
  ok   k=4: n= 95, m= 755, triangle-free, diameter 2, alpha(D2)=2, proper 7-colouring exhibited => chi/omega = 3.5, margin -1.5
  ok   k=5: n=191, m=2360, triangle-free, diameter 2, alpha(D2)=2, proper 8-colouring exhibited => chi/omega = 4.0, margin -2.0
       (chi(M(G)) = chi(G)+1 is Mycielski's theorem, 1955; combined with the
        proper colourings exhibited above this gives chi(G_k) = k+3 exactly.)

Part G -- a counterexample needs chi > omega^2, so 23 is near-minimal
  ok   alpha(D2) >= omega on 300 random connected graphs (a maximum clique is independent in D2)
  ok   hence omega=2 requires chi >= 5; the smallest triangle-free 5-chromatic graph has 22 vertices (Jensen-Royle 1995), so no counterexample has fewer than 22 vertices

Part H -- exhaustive census of all connected graphs of small order
  ok   no violation among all connected graphs of order <= 9 (min margin 0.5 from n=5 on); first equality is the Grotzsch graph at n=11, so the 10-vertex Los Alamos census of [BDF] could not see this

Part I -- source text
  ok   conjecture 135 reads as transcribed in the committed source
  ok   the D2 definition -- joined iff their distance in G is 2 -- is present verbatim in the committed source
  ok   135 is NOT fenced by the book's '* * *' marker (which the preface reserves for conjectures whose answer the author already knew), unlike 157 which is; and unlike 124 the text does not say 'Disproved by s.f.'

ALL CHECKS PASSED -- conjecture 135 is FALSE.