A new heuristic for finding verifiable k-vertex-critical subgraphs

Given graph G, a k-vertex-critical subgraph (k-VCS) $$H \subseteq G$$ H ⊆ G is a subgraph with chromatic number $$\chi (H)=k$$ χ ( H ) = k , for which no vertex can be removed without decreasing its chromatic number. The main motivation for finding a k-VCS is to prove k is a lower bound on $$\chi (G)$$ χ ( G ) . A graph may have several k-VCSs, and the k-Vertex-Critical Subgraph Problem asks for one with the least possible vertices. We propose a new heuristic for this problem. Differently from typical approaches that modify candidate subgraphs on a vertex-by-vertex basis, it generates new subgraphs by a heuristic that optimizes for maximum edges. We show this strategy has several advantages, as it allows a greater focus on smaller subgraphs for which computing $$\chi $$ χ is less of a bottleneck. Experimentally the proposed method matches or improves previous results in nearly all cases, and more often finds solutions that are provenly k-VCSs. We find new best k-VCSs for several DIMACS instances, and further improve known lower bounds for the chromatic number in two open instances, also fixing their chromatic numbers by matching existing upper bounds.