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