Title | ||
---|---|---|
On the connection between chromatic number, maximal clique and minimal degree of a graph |
Abstract | ||
---|---|---|
Let G\"n be a graph of n vertices, having chromatic number r which contains no complete graph of r vertices. Then G\"n contains a vertex of degree not exceeding n(3r-7)/(3r-4). The result is essentially best possible. |
Year | DOI | Venue |
---|---|---|
1974 | 10.1016/0012-365X(74)90133-2 | Discrete Mathematics |
DocType | Volume | Issue |
Journal | 8 | 3 |
ISSN | Citations | PageRank |
Discrete Mathematics | 56 | 13.16 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
B. Andrásfai | 1 | 56 | 13.16 |
P Erdös | 2 | 626 | 190.85 |
V.T. Sós | 3 | 77 | 50.47 |