Certified Bounds on the Fractional Chromatic Number of Planar Graphs by Learned Subgraph Selection: code, instances and certificates

Abstract

Code, instances, certificates and results for the paper "Certified Bounds on the Fractional Chromatic Number of Planar Graphs by Learned Subgraph Selection". The method computes certified lower bounds on the fractional chromatic number of planar graphs. A graph neural network ranks vertices, a small induced subgraph is taken from that ranking and solved exactly, and the result is issued as an integer certificate. Because the fractional chromatic number is monotone under induced subgraphs, validity does not depend on the quality of the ranking. This archive contains the source code, the instance generators with their fixed seeds, the mined hard instances as graph6 strings, one certificate per instance holding both the dual vector and an explicit (a:b)-colouring, an environment lockfile, per-instance result tables and the raw logs. Certificates can be checked without running any of this code: each is a vertex set, a vector of integers and one integer denominator, verifiable by a loop over the edges. Contents: 289 files. Running pytest from the extracted archive gives 469 passed, 25 skipped, 0 failed.