Semi-strong chromatic number of a graph. (English) Zbl 0820.05024
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 |\).
Reviewer: M.Kubale (Gdańsk)
MSC:
05C15 | Coloring of graphs and hypergraphs |
05C35 | Extremal problems in graph theory |
05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
05C75 | Structural characterization of families of graphs |