AN UPPER BOUND ON THE CHROMATIC NUMBER OF A GRAPH,
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1969
- Accession Number
- AD0684527
Entities
People
- Jon H. Folkman
Organizations
- RAND Corporation