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