Accession Number : AD0684527

Title :   AN UPPER BOUND ON THE CHROMATIC NUMBER OF A GRAPH,

Corporate Author : RAND CORP SANTA MONICA CALIF

Personal Author(s) : Folkman,Jon H.

Report Date : FEB 1969

Pagination or Media Count : 35

Abstract : A proof is provided for a graph-theoretic conjecture of Erdos and Hajnal, as follows. Let G be a graph and let k be a nonnegative integer. Suppose that for each set S included in V(G) there is a set T included in S such that T is independent in G and the cardinality of T is greater than or equal to one half the cardinality of S minus k. Then G may be vertex colored in k plus 2 colors. (Author)

Descriptors :   (*GRAPHICS, *COMBINATORIAL ANALYSIS), SET THEORY, COLORS, THEOREMS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE