| Article ID: | iaor20051025 |
| Country: | Germany |
| Volume: | 1 |
| Issue: | 1 |
| Start Page Number: | 43 |
| End Page Number: | 50 |
| Publication Date: | Jan 2003 |
| Journal: | 4OR |
| Authors: | Nuffelen C. Van, Rompay K. Van |
New upper bounds for the independence number and for the clique covering number of a graph are given in terms of the rank, respectively the eigenvalues, of the adjacency matrix. We formulate a conjecture concerning an upper bound of the clique covering number. This upper bound is related to an old conjecture of Alan J. Hoffman which is shown to be false.