Treffer: Dominator Coloring in Brick Product Graphs: Bounds, Constructions, and Applications.

Dominator coloring extends classical graph coloring by requiring each color class to contain at least one vertex that dominates all vertices within that class. Situated at the intersection of graph coloring and domination theory, it provides a unified framework for modeling supervision, resource allocation, and control in networked systems such as wireless sensor networks, distributed schedulers, and modular computing architectures. This paper investigates the dominator coloring on brick product graphs--a generalized graph product that integrates the structural characteristics of Cartesian and strong products. We establish new upper and lower bounds, along with exact values of the dominator chromatic number χd(G), for paths, cycles, and grids, and extend these results analytically to brick products. The problem of determining χd(G) has been shown to be NP-complete and remains NPhard even for planar and bipartite graphs. To address this computational intractability, a greedy neighborhood-expansion algorithm with a correctness guarantee is proposed, complemented by an integer linear programming (ILP) formulation for exact solutions on small instances. Comparative evaluation with Roman and k-distance dominator colorings highlights the tradeoffs among redundancy, coverage radius, and computational effort. Numerical experiments on structured product graphs demonstrate that dominator-based colorings can effectively enhance resilience, coordination, and communication efficiency in large-scale network applications. [ABSTRACT FROM AUTHOR]