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

Alex Gliesch () and Marcus Ritt ()
Additional contact information
Alex Gliesch: Federal University of Rio Grande do Sul
Marcus Ritt: Federal University of Rio Grande do Sul

Journal of Heuristics, 2022, vol. 28, issue 1, No 3, 91 pages

Abstract: Abstract 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.

Keywords: Critical subgraphs; Graph coloring; Heuristic algorithm; Iterated tabu search (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-021-09487-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:28:y:2022:i:1:d:10.1007_s10732-021-09487-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-021-09487-9

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().