Clique minors and fractional clique covers in graphs with independence number two
The paper’s certificate splits the 100 vertices of H, the complement of the Higman-Sims graph, into 56 connected groups: 12 single vertices and 44 pairs joined by an edge.
What the paper shows and what it does not claim
Shows
Every graph G with α(G) ≤ 2 has an odd-order induced subgraph F and an integer b ≥ 0 with χ(G) = b + (|F| + 1)/2 and h(G) ≥ b + h(F).
Fractional clique covering number at most four implies h(G) ≥ χ(G) − 1, and θf(G) < 31/8 implies Hadwiger’s inequality.
For the complement H of the Higman-Sims graph: h(H[w]) ≥ ⌊(24χ(H[w]) − 12)/25⌋ for every clique inflation, and h(H[S]) ≥ χ(H[S]) − 2 for every induced subgraph.
Does not claim
Hadwiger’s inequality itself is reached only below fractional clique covering number 31/8.
For graphs with independence number two, we turn clique-minor bounds into chromatic bounds without accumulating error, and apply them to Hadwiger’s conjecture.
- Field
- Mathematics, graph theory
- Published
- 19 October 2026 on Zenodo
- License
- CC BY 4.0
- File
- 11 pages, 306 KB
Abstract
For graphs with independence number at most two, we convert bounds on clique minors in terms of order into chromatic bounds without accumulating an error across the join factors of a critical graph. Every such graph G has an odd-order induced subgraph F and an integer b ≥ 0 such that χ(G) = b + (|F| + 1)/2 and h(G) ≥ b + h(F). Consequently, the largest hereditary deficit χ − h equals the largest hereditary deficit ⌈|V|/2⌉ − h. Combining this reduction with the Chudnovsky-Seymour half-order bound gives h(G) ≥ ⌊((2 + 4 min{1/4, 1/T})/3)(χ(G) − 1/2)⌋ when θf(G) ≤ T.
Thus fractional clique covering number at most four implies h(G) ≥ χ(G) − 1, while θf(G) < 31/8 implies Hadwiger’s inequality. For each T < 4, any counterexample with θf(G) ≤ T contains an induced counterexample whose order is bounded in terms of T. Applied to the complement H of the Higman-Sims graph, the method yields h(H[w]) ≥ ⌊(24χ(H[w]) − 12)/25⌋ for every clique inflation and h(H[S]) ≥ χ(H[S]) − 2 for every induced subgraph.
Cite
@misc{mantisdiscovery_23484533, title = {Clique minors and fractional clique covers in graphs with independence number two}, author = {{Mantis Discovery}}, year = {2026}, publisher = {Zenodo}, doi = {10.5281/zenodo.23484533}}