Accession Number:

AD0684527

Title:

AN UPPER BOUND ON THE CHROMATIC NUMBER OF A GRAPH,

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CALIF

Personal Author(s):

Report Date:

1969-02-01

Pagination or Media Count:

35.0

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE