Inequalities between the domination number and the chromatic number of a graph (Q1121277)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Inequalities between the domination number and the chromatic number of a graph |
scientific article |
Statements
Inequalities between the domination number and the chromatic number of a graph (English)
0 references
1989
0 references
The following inequalities between the domination number \(\sigma\) and the chromatic number \(\chi\) of a (simple) graph on p vertices are proved by a direct application and combination of several old and newer results on these parameters: For all graphs G it holds \(\sigma +\chi \leq p+1\) with equality if and only if \(G\cong K_ p.\) For all connected graphs G with \(p\geq 5\) it holds \(\sigma\) \(\chi\leq \frac{p^ 2}{4}\) with equality if and only if G consists of a \(K_{p/2}\) (p even) each of whose vertices is connected with an endvertex. For all regular graphs with \(p\geq 5\) it holds \(\sigma\) \(\chi\leq \frac{6}{25}p^ 2\) with equality if and only if \(G\cong C_ 5\).
0 references
finite simple graph
0 references
complementarity relation
0 references
domination number
0 references
chromatic number
0 references
connected graphs
0 references
regular graphs
0 references