Ramseyan properties of graphs (Q1379170)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Ramseyan properties of graphs |
scientific article |
Statements
Ramseyan properties of graphs (English)
0 references
22 February 1998
0 references
Summary: Every graph of chromatic number \(k\) with more than \(k(r-1)(b-1)\) vertices has a \(b\)-element independent set of vertices such that if any two of them are joined by an edge then the chromatic number stays the same or an \(r\)-element independent set of vertices such that joining any two of them by an edge increases the chromatic number.
0 references
Ramsey graph
0 references
chromatic number
0 references
independent set
0 references
