Graph factorization and theorems of the Nordhaus-Gaddum class (Q802576)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Graph factorization and theorems of the Nordhaus-Gaddum class
scientific article

    Statements

    Graph factorization and theorems of the Nordhaus-Gaddum class (English)
    0 references
    0 references
    1984
    0 references
    \textit{E. A. Nordhaus} and \textit{J. W. Gaddum} [Am. Math. Mon. 63, 175-177 (1956; Zbl 0070.185)] proved lower and upper bounds for the sum and product of the chromatic number of complementary graphs. \textit{G. A. Dirac} [J. Lond. Math. Soc. 39, 451-454 (1964; Zbl 0126.393)] gave a more general upper bound for the sum of the chromatic numbers of two subgraphs of \(k_ p\) having \(\ell\) edges in common. \textit{J. Plesník} [J. Graph Theory 2, 9-17 (1978; Zbl 0375.05027)] gave upper and lower bounds for the sum and product of the chromatic number of n factors of \(k_ p\). In this paper analogues of the Dirac and Plesnik results are given for point and line connectivity and for Lick-White point partition numbers. Similar work for point partition numbers has been done by \textit{M. Borowiecki} [Point partition numbers and generalized Nordhaus-Gaddum problems, Colloq. Math. 48, 279-285 (1984)]. Further results similar to Plesnik's are given for the chromatic number.
    0 references
    Nordhaus-Gaddum theorem
    0 references
    graph factorization
    0 references
    chromatic number
    0 references
    line connectivity
    0 references
    point partition numbers
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references