Optimizing Safe Chemical Storage Using Graph Coloring Algorithms and Analysis

Abstract

This paper investigates the problem of safe chemical storage by leveraging vertex graph coloring. Chemical substances are modeled as vertices, with potential reactions represented as edges in an undirected graph. The objective is to minimize the number of storage groups (colors) to prevent interactions between reactive substances. We analyze two algorithms: a greedy algorithm and the DSATUR heuristic, and propose a modified approach incorporating local optimization. Numerical experiments are conducted on graphs of varying sizes and densities, with results visualized through graphs and tables. The modified algorithm reduces the number of colors by 10–20% compared to the greedy approach, maintaining acceptable computational complexity. The findings highlight the potential for practical implementation in chemical laboratories.