Semi-strong chromatic number of a graph (Q1346444)

The semi-strong chromatic number \(\chi_ s (G)\) of a graph \(G = (V,E)\) is the minimum order of a partition of \(V\) such that every set \(S\) of the partition has the property that no vertex of \(G\) has two neighbors in \(S\). The purpose of this paper is to initiate a study of \(\chi_ s (G)\). The authors determine the value of the semi-strong chromatic number for various highly-structured graphs including complete and complete bipartite graphs, wheels, trees and cycles. Also, they give tight bounds for block graphs and cacti and characterize the graphs \(G\) for which \(\chi_ s (G) = | V |\).