Exploring the Dom-Chromatic number through saliency segmentation and deep image compression

Abstract

 In graph theory, a \textit{dom-coloring set} of a $\chi$-colored graph $G = (V, E)$ is a dominating set that includes at least one vertex from every color class. This idea can be examined through the concept of saliency segmentation in image compression, where each color class is analogous to a segment with varying significance. The \textit{dom-chromatic number} $\gamma_{dc,si}(G)$ is the smallest number of vertices that dominate all color classes, similar to how salient image regions are prioritized with more bits during compression. This analogy offers a novel approach to understanding how critical regions within a graph can be efficiently covered, similar to image segmentation and compression techniques that optimize resource allocation based on importance.