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
    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
    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

    Identifiers