Semi-strong chromatic number of a graph (Q1346444)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Semi-strong chromatic number of a graph |
scientific article |
Statements
Semi-strong chromatic number of a graph (English)
0 references
4 April 1995
0 references
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 |\).
0 references
strongly stable set
0 references
degree
0 references
diameter
0 references
semi-strong chromatic number
0 references
partition
0 references
bipartite graphs
0 references
wheels
0 references
trees
0 references
cycles
0 references
tight bounds
0 references
block graphs
0 references
cacti
0 references