A 13-vertex disproof of the Annor–Howerton graph conjecture

This repository gives two explicit, nonisomorphic connected graphs that disprove Conjecture 11 in Annor–Howerton, Induced Subgraph Bounds on the Zero Forcing Number and a (χ, ω, Z)-Conjecture (arXiv:2607.20137).

The short version is:

The conjecture predicts:  χ(G) ≤ ceil((ω(G) + Z(G) + 1) / 2)

These graphs have:        χ(G) = 5,  ω(G) = 3,  Z(G) = 4
The predicted upper bound is:       ceil((3 + 4 + 1) / 2) = 4

But 5 > 4. Each graph is therefore an unconditional counterexample.

What problem are we solving?

The conjecture tried to upper-bound how hard a graph is to color using two other graph measurements:

• Chromatic number χ(G): the fewest colors needed so adjacent vertices have different colors.
• Clique number ω(G): the size of the largest set of vertices that are all adjacent to one another.
• Zero-forcing number Z(G): the smallest starting set that can color the whole graph under one local rule: a colored vertex with exactly one uncolored neighbor forces that neighbor to become colored.

The proposed universal inequality was:

χ(G) ≤ ceil((ω(G) + Z(G) + 1) / 2)

This was a plausible strengthening of the known inequality χ(G) ≤ Z(G) + 1. The preprint proves the new bound for several graph classes and reports an exhaustive check of every connected graph on at most 11 vertices—more than one billion graphs in total.

What exactly is new here?

This repository contributes four concrete results:

1. Two finite counterexamples. Each has 13 vertices, 33 edges, and the exact invariant triple (χ, ω, Z) = (5, 3, 4).
2. A structural explanation. A seven-vertex gadget forces two nonadjacent vertices to share a color in every 4-coloring. Sparse cross-edges then deny that color to a second gadget that already needs four colors.
3. An independently checkable certificate. The graph6 strings, full edge lists, forcing sequence, explicit 5-coloring, structural proof, and dependency-free exact verifier are all included.
4. An infinite family. Attaching a pendant path gives a connected counterexample of every order n ≥ 13 while preserving (χ, ω, Z) = (5, 3, 4).

The discovery was AI-assisted, but the result does not depend on trusting an AI system: the proof is self-contained and every finite claim is reproduced by exact search.

Why does the discovery matter?

• It settles the universal conjecture as false with small, explicit witnesses.
• It reveals the specific blind spot in the proposed bound: clique number and zero forcing can both stay small while a global color-equality gadget still forces a fifth color.
• It suggests that a repaired bound would need an additional structural hypothesis or a parameter capable of detecting this global coloring obstruction.
• It makes independent review unusually easy: the witnesses are machine-readable and the complete verification runs with one standard-library Python command.

The result does not invalidate the preprint’s proved theorems about induced-subgraph bounds, planar graphs, or the stated triangle-free classes. It also does not prove that 13 vertices is minimal: the preprint settles orders through 11, while order 12 remains open here.

The two witnesses

Use the vertex order:

(x0, x1, x2, x3, x4, a, b, y0, y1, y2, y3, y4, h)

Graph	Vertices	Edges	χ	ω	Z	graph6
G_a	13	33	5	3	4	Lhf~oST?gC_X@^
G_b	13	33	5	3	4	Lhf~oSR?gC_X@^

The graphs differ in one cross-edge and are nonisomorphic: G_a has maximum degree 9, while G_b has maximum degree 10.

How the construction works

Let X = {x0, x1, x2, x3, x4} and Y = {y0, y1, y2, y3, y4}, with subscripts read modulo 5.

• The left gadget consists of a 5-cycle on X plus two nonadjacent vertices a and b, each joined to every vertex in X. In every 4-coloring, a and b must share the fourth color.
• The right gadget consists of a 5-cycle on Y plus a hub h joined to every vertex in Y. This wheel requires four colors.
• Add the common cross-edges x3-y1, x4-y0, a-h, b-y0, b-y2, b-y3, and b-y4.
• Add a-y1 for G_a, or b-y1 for G_b.

Every right-gadget vertex is now adjacent to a or b. A hypothetical 4-coloring would therefore remove their shared color from the entire right gadget, leaving only three colors for a graph that needs four. That contradiction proves χ ≥ 5; the included explicit 5-coloring proves χ = 5.

Why all three values are exact

• χ = 5: the gadget argument rules out four colors, and an explicit five-coloring supplies the upper bound.
• ω = 3: triangles exist, while the sparse cross-edge structure rules out every possible mixed 4-clique.
• Z = 4: {x0, x1, x4, a} forces the whole graph. Minimum degree 4 rules out any starting set of at most three vertices because no first force could occur.

The full 8-page research note gives the complete proof, diagrams, chronological forcing sequence, adjacency lists, graph6 encodings, verification methodology, limitations, and references. An editable DOCX and a compact 4-page note are also available.

Reproduce every claim

The verifier uses only the Python standard library and exact finite search:

python3 verify_chi_omega_Z_counterexamples.py

Expected output:

G_a: n=13, m=33, omega=3, chi=5, Z=4
G_b: n=13, m=33, omega=3, chi=5, Z=4
All exact checks passed.

It reconstructs both graphs and checks connectivity, order, size, degree data, graph6 encodings, chromatic number, clique number, zero-forcing number, the displayed forcing sequence, and the strict violation. The same command runs in GitHub Actions on every push and pull request.

Repository map

paper/      full research note, editable DOCX, and compact LaTeX note
data/       graph6 witnesses and complete edge lists
figures/    light-mode diagrams and seven X-thread cards
scripts/    reproducible artwork generator
.github/    exact CI verification
THREAD.md   humanized seven-post X thread

See paper/README.md for the document guide and SHA256SUMS for artifact hashes.

Research status and attribution

The counterexamples and their verification are exact. The cited preprint was submitted on 22 July 2026; this note was prepared on 24 July 2026. Historical priority should remain provisional until the authors or other specialists independently review the result.

If you use these witnesses, cite this repository through CITATION.cff and cite the original conjecture as:

D. Y. B. Annor and B. Howerton, “Induced Subgraph Bounds on the Zero Forcing Number and a (χ, ω, Z)-Conjecture,” arXiv:2607.20137, 2026.

License

Code is released under the MIT License. The mathematical statements, graph data, and generated figures are released under CC0 1.0.